A184960 - OEIS

%I #28 May 01 2014 02:37:01

%S 1,1,4,21,266,7848,1,367860,0,21609299,1,1470293674,1,113314233799,9,

%T 9799685588930,6

%N Irregular triangle C(n,g) read by rows, counting the connected 6-regular simple graphs on n vertices with girth exactly g.

%C The first column is for girth exactly 3. The row length sequence starts: 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3. The row length is incremented to g-2 when n reaches A054760(6,g).

%H Andries E. Brouwer, <a href="http://www.win.tue.nl/~aeb/graphs/cages/cages.html">Cages</a>

%H Jason Kimberley, <a href="/wiki/User:Jason_Kimberley/C_k-reg_girth_eq_g_index">Index of sequences counting connected k-regular simple graphs with girth exactly g</a>

%H Jason Kimberley, <a href="/A184960/a184960_1.txt">Incomplete table of i, n, g, C(n,g)=a(i) for row n = 7..42</a>

%e Triangle begins:

%e 1;

%e 1;

%e 4;

%e 21;

%e 266;

%e 7848, 1;

%e 367860, 0;

%e 21609299, 1;

%e 1470293674, 1;

%e 113314233799, 9;

%e 9799685588930, 6;

%e ?, 267;

%e ?, 3727;

%e ?, 483012;

%e ?, 69823723;

%e ?, 14836130862;

%e The C(40,5)=1 (see the a-file) graph, the unique (6,5)-cage, is the complement of a Petersen graph inside the Hoffman-Singleton graph [from Brouwer link].

%e The first known of C(42,5)>=1 graph(s) has automorphism group of order 5040 and these adjacency lists:

%e 1 : 2 3 4 5 6 7

%e 2 : 1 8 9 10 11 12

%e 3 : 1 13 14 15 16 17

%e 4 : 1 18 19 20 21 22

%e 5 : 1 23 24 25 26 27

%e 6 : 1 28 29 30 31 32

%e 7 : 1 33 34 35 36 37

%e 8 : 2 13 18 23 28 38

%e 9 : 2 14 19 24 33 39

%e 10 : 2 15 20 29 34 40

%e 11 : 2 16 25 30 35 41

%e 12 : 2 21 26 31 36 42

%e 13 : 3 8 21 27 34 41

%e 14 : 3 9 26 28 37 40

%e 15 : 3 10 22 25 31 39

%e 16 : 3 11 19 32 36 38

%e 17 : 3 20 23 30 33 42

%e 18 : 4 8 25 32 33 40

%e 19 : 4 9 16 27 29 42

%e 20 : 4 10 17 26 35 38

%e 21 : 4 12 13 30 37 39

%e 22 : 4 15 24 28 36 41

%e 23 : 5 8 17 29 36 39

%e 24 : 5 9 22 30 34 38

%e 25 : 5 11 15 18 37 42

%e 26 : 5 12 14 20 32 41

%e 27 : 5 13 19 31 35 40

%e 28 : 6 8 14 22 35 42

%e 29 : 6 10 19 23 37 41

%e 30 : 6 11 17 21 24 40

%e 31 : 6 12 15 27 33 38

%e 32 : 6 16 18 26 34 39

%e 33 : 7 9 17 18 31 41

%e 34 : 7 10 13 24 32 42

%e 35 : 7 11 20 27 28 39

%e 36 : 7 12 16 22 23 40

%e 37 : 7 14 21 25 29 38

%e 38 : 8 16 20 24 31 37

%e 39 : 9 15 21 23 32 35

%e 40 : 10 14 18 27 30 36

%e 41 : 11 13 22 26 29 33

%e 42 : 12 17 19 25 28 34

%Y Connected 6-regular simple graphs with girth at least g: A184961 (triangle); chosen g: A006822 (g=3), A058276 (g=4).

%Y Connected 6-regular simple graphs with girth exactly g: this sequence (triangle); chosen g: A184963 (g=3), A184964 (g=4).

%Y Triangular arrays C(n,g) counting connected simple k-regular graphs on n vertices with girth exactly g: A198303 (k=3), A184940 (k=4), A184950 (k=5), this sequence (k=6), A184970 (k=7), A184980 (k=8).

%K nonn,hard,more,tabf

%O 7,3

%A _Jason Kimberley_, Feb 24 2011

%E After approximately 390 processor days of computation with genreg, C(41,5)=0.