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

1, 1, 4, 21, 266, 7848, 1, 367860, 0, 21609299, 1, 1470293674, 1, 113314233799, 9, 9799685588930, 6

Offset: 7

Author

Jason Kimberley, Feb 24 2011

Keywords

• nonn
• hard
• more
• tabf

Comments

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).

Examples

			Triangle begins:
1;
1;
4;
21;
266;
7848, 1;
367860, 0;
21609299, 1;
1470293674, 1;
113314233799, 9;
9799685588930, 6;
?, 267;
?, 3727;
?, 483012;
?, 69823723;
?, 14836130862;
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].
The first known of C(42,5)>=1 graph(s) has automorphism group of order 5040 and these adjacency lists:
1 : 2 3 4 5 6 7
2 : 1 8 9 10 11 12
3 : 1 13 14 15 16 17
4 : 1 18 19 20 21 22
5 : 1 23 24 25 26 27
6 : 1 28 29 30 31 32
7 : 1 33 34 35 36 37
8 : 2 13 18 23 28 38
9 : 2 14 19 24 33 39
10 : 2 15 20 29 34 40
11 : 2 16 25 30 35 41
12 : 2 21 26 31 36 42
13 : 3 8 21 27 34 41
14 : 3 9 26 28 37 40
15 : 3 10 22 25 31 39
16 : 3 11 19 32 36 38
17 : 3 20 23 30 33 42
18 : 4 8 25 32 33 40
19 : 4 9 16 27 29 42
20 : 4 10 17 26 35 38
21 : 4 12 13 30 37 39
22 : 4 15 24 28 36 41
23 : 5 8 17 29 36 39
24 : 5 9 22 30 34 38
25 : 5 11 15 18 37 42
26 : 5 12 14 20 32 41
27 : 5 13 19 31 35 40
28 : 6 8 14 22 35 42
29 : 6 10 19 23 37 41
30 : 6 11 17 21 24 40
31 : 6 12 15 27 33 38
32 : 6 16 18 26 34 39
33 : 7 9 17 18 31 41
34 : 7 10 13 24 32 42
35 : 7 11 20 27 28 39
36 : 7 12 16 22 23 40
37 : 7 14 21 25 29 38
38 : 8 16 20 24 31 37
39 : 9 15 21 23 32 35
40 : 10 14 18 27 30 36
41 : 11 13 22 26 29 33
42 : 12 17 19 25 28 34
		

Links

• Andries E. Brouwer, Cages
• Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth exactly g
• Jason Kimberley, Incomplete table of i, n, g, C(n,g)=a(i) for row n = 7..42

Crossrefs

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

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

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).

Extensions

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