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!)
A296620 Number of 4-regular (quartic) connected graphs on n nodes with diameter k written as irregular triangle T(n,k). 2
1, 0, 1, 0, 2, 0, 6, 0, 16, 0, 24, 35, 0, 37, 227, 1, 0, 26, 1502, 16, 0, 10, 10561, 202, 5, 0, 1, 84103, 4006, 58, 0, 1, 722252, 82726, 493, 19, 0, 0, 6383913, 1647078, 6224, 202, 1, 0, 0, 55831405, 30291536, 96504, 2156, 33 (list; graph; refs; listen; history; text; internal format)
OFFSET

5,5

COMMENTS

The results were found by applying the Floyd-Warshall algorithm to the output of Markus Meringer's GenReg program.

LINKS

Table of n, a(n) for n=5..54.

M. Meringer, GenReg, Generation of regular graphs.

Wikipedia, Distance (graph theory).

Wikipedia, Floyd-Warshall algorithm.

EXAMPLE

Triangle begins:

                     Diameter

   n/ 1  2        3        4     5    6  7

   5: 1

   6: 0  1

   7: 0  2

   8: 0  6

   9: 0 16

  10: 0 24       35

  11: 0 37      227        1x

  12: 0 26     1502       16

  13: 0 10    10561      202     5

  14: 0  1x   84103     4006    58

  15: 0  1x  722252    82726   493   19

  16: 0  0  6383913  1647078  6224  202  1x

  17: 0  0 55831405 30291536 96504 2156 33

.

x indicates provision of adjacency information below.

Examples of unique 4-regular graphs with minimum diameter:

Adjacency matrix of the graph of diameter 2 on 14 nodes:

      1 2 3 4 5 6 7 8 9 0 1 2 3 4

   1  . 1 1 1 1 . . . . . . . . .

   2  1 . . . . 1 1 1 . . . . . .

   3  1 . . . . 1 1 1 . . . . . .

   4  1 . . . . . . . 1 1 1 . . .

   5  1 . . . . . . . . . . 1 1 1

   6  . 1 1 . . . . . 1 . . 1 . .

   7  . 1 1 . . . . . . 1 . . 1 .

   8  . 1 1 . . . . . . . 1 . . 1

   9  . . . 1 . 1 . . . . . . 1 1

  10  . . . 1 . . 1 . . . . 1 . 1

  11  . . . 1 . . . 1 . . . 1 1 .

  12  . . . . 1 1 . . . 1 1 . . .

  13  . . . . 1 . 1 . 1 . 1 . . .

  14  . . . . 1 . . 1 1 1 . . . .

.

Adjacency matrix of the graph of diameter 2 on 15 nodes:

      1 2 3 4 5 6 7 8 9 0 1 2 3 4 5

   1  . 1 1 1 1 . . . . . . . . . .

   2  1 . 1 . . 1 1 . . . . . . . .

   3  1 1 . . . . . 1 1 . . . . . .

   4  1 . . . . . . . . 1 1 1 . . .

   5  1 . . . . . . . . . . . 1 1 1

   6  . 1 . . . . . . . 1 1 . 1 . .

   7  . 1 . . . . . . . . . 1 . 1 1

   8  . . 1 . . . . . . 1 . 1 . 1 .

   9  . . 1 . . . . . . . 1 . 1 . 1

  10  . . . 1 . 1 . 1 . . . . . . 1

  11  . . . 1 . 1 . . 1 . . . . 1 .

  12  . . . 1 . . 1 1 . . . . 1 . .

  13  . . . . 1 1 . . 1 . . 1 . . .

  14  . . . . 1 . 1 1 . . 1 . . . .

  15  . . . . 1 . 1 . 1 1 . . . . .

.

Examples of unique graphs with maximum diameter:

Adjacency matrix of the graph of diameter 4 on 11 nodes:

      1 2 3 4 5 6 7 8 9 0 1

   1  . 1 1 1 1 . . . . . .

   2  1 . 1 1 1 . . . . . .

   3  1 1 . 1 1 . . . . . .

   4  1 1 1 . . 1 . . . . .

   5  1 1 1 . . 1 . . . . .

   6  . . . 1 1 . 1 1 . . .

   7  . . . . . 1 . . 1 1 1

   8  . . . . . 1 . . 1 1 1

   9  . . . . . . 1 1 . 1 1

  10  . . . . . . 1 1 1 . 1

  11  . . . . . . 1 1 1 1 .

.

Adjacency matrix of the graph of diameter 7 on 16 nodes:

      1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6

   1  . 1 1 1 1 . . . . . . . . . . .

   2  1 . 1 1 1 . . . . . . . . . . .

   3  1 1 . 1 1 . . . . . . . . . . .

   4  1 1 1 . . 1 . . . . . . . . . .

   5  1 1 1 . . 1 . . . . . . . . . .

   6  . . . 1 1 . 1 1 . . . . . . . .

   7  . . . . . 1 . 1 1 1 . . . . . .

   8  . . . . . 1 1 . 1 1 . . . . . .

   9  . . . . . . 1 1 . 1 1 . . . . .

  10  . . . . . . 1 1 1 . 1 . . . . .

  11  . . . . . . . . 1 1 . 1 1 . . .

  12  . . . . . . . . . . 1 . . 1 1 1

  13  . . . . . . . . . . 1 . . 1 1 1

  14  . . . . . . . . . . . 1 1 . 1 1

  15  . . . . . . . . . . . 1 1 1 . 1

  16  . . . . . . . . . . . 1 1 1 1 .

CROSSREFS

Cf. A006820 (row sums), A204329, A294733 (number of terms in each row for odd n), A296525 (number of terms in each row for even n).

Sequence in context: A293935 A285479 A327369 * A263789 A081153 A126869

Adjacent sequences:  A296617 A296618 A296619 * A296621 A296622 A296623

KEYWORD

nonn,tabf

AUTHOR

Hugo Pfoertner, Dec 17 2017

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 July 28 00:54 EDT 2021. Contains 346316 sequences. (Running on oeis4.)