login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A343162 The number of graphs on n nodes that can be isometrically embedded in a Hamming graph. 7
1, 1, 2, 5, 11, 35, 111, 427, 1742 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Comments from Don Knuth, Apr 17 2021: (Start)

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.

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:

*        .  --  .

*      / |      | \

*    .   |      |   .

*      \ |      | /

*        .  --  .

This graph cannot be isometrically embedded in a Hamming graph. But it is an induced subgraph:

*       10  --  11

*      / |      | \

*    00  |      |  31

*      \ |      | /

*       20  --  21

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)

REFERENCES

Donald E. Knuth, The Art of Computer Programming, Volume 4B

   (in preparation). Section 7.2.2.3 will contain an exercise

   devoted to this topic.

LINKS

Table of n, a(n) for n=1..9.

Peter M. Winkler, Isometric embedding in products of complete graphs, Discrete Applied Mathematics 7 (1984), 221-225.

FORMULA

a(n) = Sum_{k=2..n} A343168(n, k). - Felix Fröhlich, Apr 22 2021

CROSSREFS

Cf. A343463, A343464, A343163-A343168.

Sequence in context: A101834 A117758 A284251 * A295495 A343463 A130622

Adjacent sequences:  A343159 A343160 A343161 * A343163 A343164 A343165

KEYWORD

nonn,more

AUTHOR

N. J. A. Sloane, Apr 19 2021, based on an email from Don Knuth

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 27 12:51 EST 2021. Contains 349394 sequences. (Running on oeis4.)