The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A343463 The number of connected graphs on n nodes that can be induced subgraphs of a Hamming graph. 7

%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

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

Last modified August 9 16:51 EDT 2024. Contains 375044 sequences. (Running on oeis4.)