|
|
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
|
|
|
|