

A343463


The number of connected graphs on n nodes that can be induced subgraphs of a Hamming graph.


7




OFFSET

1,3


COMMENTS

A Hamming graph is a Cartesian product of complete graphs. Each vertex is named by a sequence of coordinates. Two vertices are adjacent if they differ in exactly one coordinate. The induced subgraph need not preserve distance, only adjacency.


REFERENCES

D. E. Knuth, The Art of Computer Programming, Volume 4B (in preparation). Section 7.2.2.3 will have an exercise devoted to this topic.


LINKS



EXAMPLE

For n=4 the a(4)=5 graphs are: P4 (000,100,110,111); C4 (00,10,11,01); K31 [the claw] (000,100,010,001); K4\P3 [the paw] (00,10,01,02); K4 (00,01,02,03).


CROSSREFS



KEYWORD

nonn,more


AUTHOR



STATUS

approved



