|
%I #11 Dec 17 2017 10:06:01
%S 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,
%T 0,1,84103,4006,58,0,1,722252,82726,493,19,0,0,6383913,1647078,6224,
%U 202,1,0,0,55831405,30291536,96504,2156,33
%N Number of 4-regular (quartic) connected graphs on n nodes with diameter k written as irregular triangle T(n,k).
%C The results were found by applying the Floyd-Warshall algorithm to the output of Markus Meringer's GenReg program.
%H M. Meringer, <a href="https://sourceforge.net/projects/genreg/">GenReg</a>, Generation of regular graphs.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Distance_(graph_theory)">Distance (graph theory).</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm">Floyd-Warshall algorithm.</a>
%e Triangle begins:
%e Diameter
%e n/ 1 2 3 4 5 6 7
%e 5: 1
%e 6: 0 1
%e 7: 0 2
%e 8: 0 6
%e 9: 0 16
%e 10: 0 24 35
%e 11: 0 37 227 1x
%e 12: 0 26 1502 16
%e 13: 0 10 10561 202 5
%e 14: 0 1x 84103 4006 58
%e 15: 0 1x 722252 82726 493 19
%e 16: 0 0 6383913 1647078 6224 202 1x
%e 17: 0 0 55831405 30291536 96504 2156 33
%e .
%e x indicates provision of adjacency information below.
%e Examples of unique 4-regular graphs with minimum diameter:
%e Adjacency matrix of the graph of diameter 2 on 14 nodes:
%e 1 2 3 4 5 6 7 8 9 0 1 2 3 4
%e 1 . 1 1 1 1 . . . . . . . . .
%e 2 1 . . . . 1 1 1 . . . . . .
%e 3 1 . . . . 1 1 1 . . . . . .
%e 4 1 . . . . . . . 1 1 1 . . .
%e 5 1 . . . . . . . . . . 1 1 1
%e 6 . 1 1 . . . . . 1 . . 1 . .
%e 7 . 1 1 . . . . . . 1 . . 1 .
%e 8 . 1 1 . . . . . . . 1 . . 1
%e 9 . . . 1 . 1 . . . . . . 1 1
%e 10 . . . 1 . . 1 . . . . 1 . 1
%e 11 . . . 1 . . . 1 . . . 1 1 .
%e 12 . . . . 1 1 . . . 1 1 . . .
%e 13 . . . . 1 . 1 . 1 . 1 . . .
%e 14 . . . . 1 . . 1 1 1 . . . .
%e .
%e Adjacency matrix of the graph of diameter 2 on 15 nodes:
%e 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
%e 1 . 1 1 1 1 . . . . . . . . . .
%e 2 1 . 1 . . 1 1 . . . . . . . .
%e 3 1 1 . . . . . 1 1 . . . . . .
%e 4 1 . . . . . . . . 1 1 1 . . .
%e 5 1 . . . . . . . . . . . 1 1 1
%e 6 . 1 . . . . . . . 1 1 . 1 . .
%e 7 . 1 . . . . . . . . . 1 . 1 1
%e 8 . . 1 . . . . . . 1 . 1 . 1 .
%e 9 . . 1 . . . . . . . 1 . 1 . 1
%e 10 . . . 1 . 1 . 1 . . . . . . 1
%e 11 . . . 1 . 1 . . 1 . . . . 1 .
%e 12 . . . 1 . . 1 1 . . . . 1 . .
%e 13 . . . . 1 1 . . 1 . . 1 . . .
%e 14 . . . . 1 . 1 1 . . 1 . . . .
%e 15 . . . . 1 . 1 . 1 1 . . . . .
%e .
%e Examples of unique graphs with maximum diameter:
%e Adjacency matrix of the graph of diameter 4 on 11 nodes:
%e 1 2 3 4 5 6 7 8 9 0 1
%e 1 . 1 1 1 1 . . . . . .
%e 2 1 . 1 1 1 . . . . . .
%e 3 1 1 . 1 1 . . . . . .
%e 4 1 1 1 . . 1 . . . . .
%e 5 1 1 1 . . 1 . . . . .
%e 6 . . . 1 1 . 1 1 . . .
%e 7 . . . . . 1 . . 1 1 1
%e 8 . . . . . 1 . . 1 1 1
%e 9 . . . . . . 1 1 . 1 1
%e 10 . . . . . . 1 1 1 . 1
%e 11 . . . . . . 1 1 1 1 .
%e .
%e Adjacency matrix of the graph of diameter 7 on 16 nodes:
%e 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
%e 1 . 1 1 1 1 . . . . . . . . . . .
%e 2 1 . 1 1 1 . . . . . . . . . . .
%e 3 1 1 . 1 1 . . . . . . . . . . .
%e 4 1 1 1 . . 1 . . . . . . . . . .
%e 5 1 1 1 . . 1 . . . . . . . . . .
%e 6 . . . 1 1 . 1 1 . . . . . . . .
%e 7 . . . . . 1 . 1 1 1 . . . . . .
%e 8 . . . . . 1 1 . 1 1 . . . . . .
%e 9 . . . . . . 1 1 . 1 1 . . . . .
%e 10 . . . . . . 1 1 1 . 1 . . . . .
%e 11 . . . . . . . . 1 1 . 1 1 . . .
%e 12 . . . . . . . . . . 1 . . 1 1 1
%e 13 . . . . . . . . . . 1 . . 1 1 1
%e 14 . . . . . . . . . . . 1 1 . 1 1
%e 15 . . . . . . . . . . . 1 1 1 . 1
%e 16 . . . . . . . . . . . 1 1 1 1 .
%Y 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).
%K nonn,tabf
%O 5,5
%A _Hugo Pfoertner_, Dec 17 2017
| 