%I #21 Apr 19 2021 02:14:02
%S 1,1,2,5,11,36,117,469,2023
%N The number of connected graphs on n nodes that can be induced subgraphs of a Hamming graph.
%C 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.
%D 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.
%e 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).
%Y Cf. A343464, A343162.
%K nonn,more
%O 1,3
%A _Don Knuth_, Apr 16 2021
