Tables and Results

From Combinatorics Wiki

Revision as of 14:39, 3 January 2019 by Grahame (talk | contribs) (1 revision imported)

Trivalent cages

Table 1: known trivalent cages

g 5 6 7 8 9 10 11 12
n(3,g) 10 14 24 30 58 70 112 126
number of cages 1 1 1 1 18 3 1 1

Table 2: bounds for trivalent cages

Optimal graphs are marked in bold

Girth g Lower bound Upper bound Number of cages Author or description
5 10 10 1 Petersen
6 14 14 1 Heawood
7 24 24 1 McGee
8 30 30 1 Tutte
9 58 58 18 Brinkmann-McKay-Saager
10 70 70 3 O’Keefe-Wong
11 112 112 1 McKay-Myrvold; Balaban
12 126 126 1 Benson
13 202 272 McKay-Myrvold; Hoare
14 258 384 McKay; Exoo
15 384 620 Biggs
16 512 960 Exoo
17 768 2176 Exoo
18 1024 2560 Exoo
19 1536 4324 Hoare, H(47)
20 2048 5376 Exoo
21 3072 16028 Exoo
22 4096 16206 Biggs-Hoare, S(73)
23 6144 49326 Exoo
24 8192 49608 Bray-Parker-Rowley
25 12288 108906 Exoo
26 16384 109200 Bray-Parker-Rowley
27 24576 285852 Bray-Parker-Rowley
28 32768 415104 Bray-Parker-Rowley
29 49152 1143408 Bray-Parker-Rowley
30 65536 1227666 Biggs-Hoare, S(313)
31 98304 3649794 Bray-Parker-Rowley
32 131072 3650304 Bray-Parker-Rowley

Cages of girth 5 and 6

Optimal graphs are marked in bold.

Table 1: known cages of Girth 5

k 3 4 5 6 7
n(k,5) 10 19 30 40 50
number of cages 1 1 4 1 1

Table 2: bounds for cages of girth 5

Degree k Lower bound Upper bound Author or description
3 10 10 Petersen
4 19 19 Robertson
5 30 30 Robertson-Wegner-Wong
6 40 40 Wong
7 50 50 Hoffman-Singleton
8 67 80 Royle
9 86 96 Jørgensen
10 103 126 Exoo
11 124 156 Jørgensen
12 147 203 Exoo
13 174 240 Exoo
14 199 288 Jørgensen
15 230 312 Jørgensen
16 259 336 Jørgensen
17 294 448 Schwenk
18 327 480 Schwenk
19 364 512 Schwenk
20 403 576 Jørgensen


Table 3: bounds for cages of girth 6

Degree k Lower bound Upper bound Author or description
3 14 14 Projective Plane
4 26 26 Projective Plane
5 42 42 Projective Plane
6 62 62 Projective Plane
7 90 90 O’Keefe-Wong
8 114 114 Projective Plane
9 146 146 Projective Plane
10 182 182 Projective Plane
11 224 240 Wong
12 266 266 Projective Plane
13 314 336 Abreu-Funk-Labbate-Napolitano
14 366 366 Projective Plane
15 422 462 Abreu-Funk-Labbate-Napolitano
16 482 504 Abreu-Funk-Labbate-Napolitano
17 546 546 Projective Plane
18 614 614 Projective Plane
19 686 720 Abreu-Funk-Labbate-Napolitano
20 762 762 Projective Plane