The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #29 Apr 23 2021 05:42:33
%S 1,1,2,5,11,35,111,427,1742
%N The number of graphs on n nodes that can be isometrically embedded in a Hamming graph.
%C Comments from _Don Knuth_, Apr 17 2021: (Start)
%C Peter Winkler (1984) found a very nice way to decide whether a given graph can be isometrically embedded into a Hamming graph. He discovered that such an embedding is actually unique, when it exists.
%C Sequence A343463 and A343464 are about graphs that are embeddable as INDUCED subgraphs. The two concepts are quite distinct. Today I may have discovered for the first time the (unique) smallest graph that proves the distinction. This is the six-node graph:
%C * . -- .
%C * / | | \
%C * . | | .
%C * \ | | /
%C * . -- .
%C This graph cannot be isometrically embedded in a Hamming graph. But it is an induced subgraph:
%C * 10 -- 11
%C * / | | \
%C * 00 | | 31
%C * \ | | /
%C * 20 -- 21
%C Sequence A343168 is a triangular array that gives the number of graphs on n vertices that are isometrically embeddable in the Hamming graph H(n,k). The present sequence gives the row sums of this triangle, and is a direct analog of A343463. The present sequence and A343463 agree up to n=5, and the graph above is the first difference between them. (End)
%D Donald E. Knuth, The Art of Computer Programming, Volume 4B
%D (in preparation). Section 7.2.2.3 will contain an exercise
%D devoted to this topic.
%H Peter M. Winkler, <a href="https://doi.org/10.1016/0166-218X(84)90069-6">Isometric embedding in products of complete graphs</a>, Discrete Applied Mathematics 7 (1984), 221-225.
%F a(n) = Sum_{k=2..n} A343168(n, k). - _Felix Fröhlich_, Apr 22 2021
%Y Cf. A343463, A343464, A343163-A343168.
%K nonn,more
%O 1,3
%A _N. J. A. Sloane_, Apr 19 2021, based on an email from _Don Knuth_