Tables and Results - Revision history

Grahame: /* Table 2: bounds for cages of girth 5 */

2025-05-13T09:05:04Z

‎Table 2: bounds for cages of girth 5

Grahame: /* Table 2: bounds for cages of girth 5 */

2025-05-12T22:30:11Z

‎Table 2: bounds for cages of girth 5

Grahame: /* Table 2: bounds for trivalent cages */

2025-05-02T17:10:48Z

‎Table 2: bounds for trivalent cages

Grahame: /* Table 3: bounds for cages of girth 6 */

2025-03-20T17:59:13Z

‎Table 3: bounds for cages of girth 6

Grahame: /* Table 2: bounds for trivalent cages */

2022-01-21T15:19:23Z

‎Table 2: bounds for trivalent cages

Grahame: /* Table 2: bounds for trivalent cages */

2019-09-16T12:14:59Z

‎Table 2: bounds for trivalent cages

Grahame: 1 revision imported

2019-01-03T14:39:32Z

1 revision imported

CW>Eyal at 23:24, 16 January 2009

2009-01-16T23:24:25Z

New page

==Trivalent cages==
===Table 1: known trivalent cages===
<center>
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"
|-
|style="background-color: #cccccc;"| ''' ''g'' ''' || style="background-color: #cccccc;" | '''5''' || style="background-color: #cccccc;" | '''6'''|| style="background-color: #cccccc;" | '''7'''|| style="background-color: #cccccc;" | '''8'''|| style="background-color: #cccccc;" | '''9'''|| style="background-color: #cccccc;" | '''10'''|| style="background-color: #cccccc;" | '''11'''|| style="background-color: #cccccc;" | '''12'''
|-
|style="background-color: #cccccc;"| ''' ''n(3,g)'' ''' || 10 ||14 ||24 ||30 ||58 ||70 ||112 ||126
|-
|style="background-color: #cccccc;"| '''number of cages'''|| 1|| 1|| 1|| 1|| 18|| 3|| 1|| 1
|}
</center>

===Table 2: bounds for trivalent cages===
Optimal graphs are marked in bold
<center>
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"
|-
|style="background-color: #cccccc;"| ''' Girth ''g'' ''' ||style="background-color: #cccccc;"| ''' Lower bound ''' ||style="background-color: #cccccc;"| ''' Upper bound ''' ||style="background-color: #cccccc;"| ''' Number of cages''' || style="background-color: #cccccc;"| ''' Author or description '''
|-
|style="background-color: #cccccc;"| 5 ||style="background-color: #cccccc;"| 10 || '''10''' ||1 ||[http://en.wikipedia.org/wiki/Petersen_graph Petersen]
|-
|style="background-color: #cccccc;"| 6 ||style="background-color: #cccccc;"| 14 ||'''14'''|| 1 ||[http://en.wikipedia.org/wiki/Heawood_graph Heawood]
|-
|style="background-color: #cccccc;"| 7 ||style="background-color: #cccccc;"| 24 || '''24''' ||1 ||McGee
|-
|style="background-color: #cccccc;"| 8 ||style="background-color: #cccccc;"| 30 ||'''30'''|| 1 ||[http://en.wikipedia.org/wiki/Tutte_eight_cage Tutte]
|-
|style="background-color: #cccccc;"| 9 ||style="background-color: #cccccc;"| 58 ||'''58''' ||18 ||Brinkmann-McKay-Saager
|-
|style="background-color: #cccccc;"| 10 ||style="background-color: #cccccc;"| 70 ||'''70''' ||3 ||O’Keefe-Wong
|-
|style="background-color: #cccccc;"| 11 ||style="background-color: #cccccc;"| 112 || '''112'''|| 1 ||McKay-Myrvold; Balaban
|-
|style="background-color: #cccccc;"| 12 ||style="background-color: #cccccc;"| 126 || '''126'''|| 1|| Benson
|-
|style="background-color: #cccccc;"| 13 ||style="background-color: #cccccc;"| 202 ||272|| ||McKay-Myrvold; Hoare
|-
|style="background-color: #cccccc;"| 14 ||style="background-color: #cccccc;"| 258 ||384 ||||McKay; Exoo
|-
|style="background-color: #cccccc;"| 15 ||style="background-color: #cccccc;"| 384 ||620|||| Biggs
|-
|style="background-color: #cccccc;"| 16 ||style="background-color: #cccccc;"| 512 ||960|| ||Exoo
|-
|style="background-color: #cccccc;"| 17 ||style="background-color: #cccccc;"| 768 ||2176|| ||Exoo
|-
|style="background-color: #cccccc;"| 18 ||style="background-color: #cccccc;"| 1024 ||2560|| ||Exoo
|-
|style="background-color: #cccccc;"| 19 ||style="background-color: #cccccc;"| 1536 ||4324|||| Hoare, H(47)
|-
|style="background-color: #cccccc;"| 20 ||style="background-color: #cccccc;"| 2048 || 5376 || ||Exoo
|-
|style="background-color: #cccccc;"| 21 ||style="background-color: #cccccc;"| 3072 ||16028 || ||Exoo
|-
|style="background-color: #cccccc;"| 22 ||style="background-color: #cccccc;"| 4096 || 16206|| || Biggs-Hoare, S(73)
|-
|style="background-color: #cccccc;"| 23 ||style="background-color: #cccccc;"| 6144 ||49326 || ||Exoo
|-
|style="background-color: #cccccc;"| 24 ||style="background-color: #cccccc;"| 8192 || 49608 || ||Bray-Parker-Rowley
|-
|style="background-color: #cccccc;"| 25 ||style="background-color: #cccccc;"| 12288 ||108906|| || Exoo
|-
|style="background-color: #cccccc;"| 26 ||style="background-color: #cccccc;"| 16384 || 109200 || ||Bray-Parker-Rowley
|-
|style="background-color: #cccccc;"| 27 ||style="background-color: #cccccc;"| 24576 ||285852 || ||Bray-Parker-Rowley
|-
|style="background-color: #cccccc;"| 28 ||style="background-color: #cccccc;"| 32768 ||415104|| || Bray-Parker-Rowley
|-
|style="background-color: #cccccc;"| 29 ||style="background-color: #cccccc;"| 49152 ||1143408|| || Bray-Parker-Rowley
|-
|style="background-color: #cccccc;"| 30 ||style="background-color: #cccccc;"| 65536 ||1227666|| || Biggs-Hoare, S(313)
|-
|style="background-color: #cccccc;"| 31 ||style="background-color: #cccccc;"| 98304 ||3649794 || ||Bray-Parker-Rowley
|-
|style="background-color: #cccccc;"| 32 ||style="background-color: #cccccc;"| 131072 ||3650304|| || Bray-Parker-Rowley
|}
</center>

==Cages of girth 5 and 6==
Optimal graphs are marked in bold.
===Table 1: known cages of Girth 5===
<center>
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"
|-
|style="background-color: #cccccc;"| ''' ''k'' ''' || style="background-color: #cccccc;" | 3 || style="background-color: #cccccc;" | 4 || style="background-color: #cccccc;" | '''5''' || style="background-color: #cccccc;" | '''6'''|| style="background-color: #cccccc;" | '''7'''
|-
|style="background-color: #cccccc;"| ''' ''n(k,5)'' ''' || 10 || 19|| 30|| 40|| 50
|-
|style="background-color: #cccccc;"| '''number of cages'''|| 1|| 1|| 4|| 1|| 1
|}
</center>

===Table 2: bounds for cages of girth 5===
<center>
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"
|-
|style="background-color: #cccccc;"| ''' Degree ''k'' ''' ||style="background-color: #cccccc;"| ''' Lower bound ''' ||style="background-color: #cccccc;"| ''' Upper bound ''' || style="background-color: #cccccc;"| ''' Author or description '''
|-
|style="background-color: #cccccc;"|3 ||style="background-color: #cccccc;"|10 ||'''10'''|| [http://en.wikipedia.org/wiki/Petersen_graph Petersen]
|-
|style="background-color: #cccccc;"|4 ||style="background-color: #cccccc;"|19 ||'''19'''|| Robertson
|-
|style="background-color: #cccccc;"|5 ||style="background-color: #cccccc;"|30 ||'''30'''|| Robertson-Wegner-Wong
|-
|style="background-color: #cccccc;"|6 ||style="background-color: #cccccc;"|40 ||'''40'''|| Wong
|-
|style="background-color: #cccccc;"|7 ||style="background-color: #cccccc;"|50||''' 50'''|| [http://en.wikipedia.org/wiki/Hoffman-Singleton_graph Hoﬀman-Singleton]
|-
|style="background-color: #cccccc;"|8 ||style="background-color: #cccccc;"|67|| 80|| Royle
|-
|style="background-color: #cccccc;"|9 ||style="background-color: #cccccc;"|86|| 96 ||Jørgensen
|-
|style="background-color: #cccccc;"|10 ||style="background-color: #cccccc;"|103|| 126 ||Exoo
|-
|style="background-color: #cccccc;"|11 ||style="background-color: #cccccc;"|124 ||156|| Jørgensen
|-
|style="background-color: #cccccc;"|12 ||style="background-color: #cccccc;"|147|| 203|| Exoo
|-
|style="background-color: #cccccc;"|13 ||style="background-color: #cccccc;"|174 ||240 ||Exoo
|-
|style="background-color: #cccccc;"|14 ||style="background-color: #cccccc;"|199 ||288 ||Jørgensen
|-
|style="background-color: #cccccc;"|15 ||style="background-color: #cccccc;"|230 ||312 ||Jørgensen
|-
|style="background-color: #cccccc;"|16 ||style="background-color: #cccccc;"|259 ||336|| Jørgensen
|-
|style="background-color: #cccccc;"|17 ||style="background-color: #cccccc;"|294|| 448 ||Schwenk
|-
|style="background-color: #cccccc;"|18 ||style="background-color: #cccccc;"|327|| 480|| Schwenk
|-
|style="background-color: #cccccc;"|19 ||style="background-color: #cccccc;"|364|| 512|| Schwenk
|-
|style="background-color: #cccccc;"|20 ||style="background-color: #cccccc;"|403|| 576 ||Jørgensen
|}
</center>

===Table 3: bounds for cages of girth 6===
<center>
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"
|-
|style="background-color: #cccccc;"| ''' Degree ''k'' ''' ||style="background-color: #cccccc;"| ''' Lower bound ''' ||style="background-color: #cccccc;"| ''' Upper bound ''' || style="background-color: #cccccc;"| ''' Author or description '''
|-
|style="background-color: #cccccc;"|3 ||style="background-color: #cccccc;"| 14 ||'''14'''|| [http://en.wikipedia.org/wiki/Projective_plane Projective Plane]
|-
|style="background-color: #cccccc;"|4 ||style="background-color: #cccccc;"|26 ||'''26'''|| Projective Plane
|-
|style="background-color: #cccccc;"|5 ||style="background-color: #cccccc;"|42 ||'''42'''|| Projective Plane
|-
|style="background-color: #cccccc;"|6 ||style="background-color: #cccccc;"|62 ||'''62'''|| Projective Plane
|-
|style="background-color: #cccccc;"|7 ||style="background-color: #cccccc;"|90 ||'''90'''|| O’Keefe-Wong
|-
|style="background-color: #cccccc;"|8 ||style="background-color: #cccccc;"|114 ||'''114'''|| Projective Plane
|-
|style="background-color: #cccccc;"|9 ||style="background-color: #cccccc;"|146 ||'''146'''|| Projective Plane
|-
|style="background-color: #cccccc;"|10 ||style="background-color: #cccccc;"|182 ||'''182'''|| Projective Plane
|-
|style="background-color: #cccccc;"|11 ||style="background-color: #cccccc;"|224 ||240|| Wong
|-
|style="background-color: #cccccc;"|12 ||style="background-color: #cccccc;"|266|| 266|| Projective Plane
|-
|style="background-color: #cccccc;"|13 ||style="background-color: #cccccc;"|314 ||336|| Abreu-Funk-Labbate-Napolitano
|-
|style="background-color: #cccccc;"|14 ||style="background-color: #cccccc;"|366 ||'''366'''|| Projective Plane
|-
|style="background-color: #cccccc;"|15 ||style="background-color: #cccccc;"|422 ||462|| Abreu-Funk-Labbate-Napolitano
|-
|style="background-color: #cccccc;"|16 ||style="background-color: #cccccc;"|482 ||504|| Abreu-Funk-Labbate-Napolitano
|-
|style="background-color: #cccccc;"|17 ||style="background-color: #cccccc;"|546 ||'''546'''|| Projective Plane
|-
|style="background-color: #cccccc;"|18 ||style="background-color: #cccccc;"|614 ||'''614'''|| Projective Plane
|-
|style="background-color: #cccccc;"|19 ||style="background-color: #cccccc;"|686 ||720 ||Abreu-Funk-Labbate-Napolitano
|-
|style="background-color: #cccccc;"|20 ||style="background-color: #cccccc;"|762 ||'''762'''|| Projective Plane
|}
</center>

[[Category:The Cage Problem]]

@@ Line 55: / Line 55: @@
 |style="background-color: #cccccc;"| 22 ||style="background-color: #cccccc;"| 4096 || 16206|| || Biggs-Hoare, S(73)
 |-
-|style="background-color: #cccccc;"| 23 ||style="background-color: #cccccc;"| 6144  ||49326 || ||Exoo
+|style="background-color: #cccccc;"| 23 ||style="background-color: #cccccc;"| 6144  ||35446 || ||Erskine-Tuite
 |-
-|style="background-color: #cccccc;"| 24 ||style="background-color: #cccccc;"| 8192 || 49608 || ||Bray-Parker-Rowley
+|style="background-color: #cccccc;"| 24 ||style="background-color: #cccccc;"| 8192 || 35640 || ||Erskine-Tuite
 |-
 |style="background-color: #cccccc;"| 25 ||style="background-color: #cccccc;"| 12288  ||108906|| || Exoo
@@ Line 65: / Line 65: @@
 |style="background-color: #cccccc;"| 27 ||style="background-color: #cccccc;"| 24576  ||285852 || ||Bray-Parker-Rowley
 |-
-|style="background-color: #cccccc;"| 28 ||style="background-color: #cccccc;"| 32768  ||415104|| || Bray-Parker-Rowley
+|style="background-color: #cccccc;"| 28 ||style="background-color: #cccccc;"| 32768  ||368640|| || Erskine-Tuite
 |-
-|style="background-color: #cccccc;"| 29 ||style="background-color: #cccccc;"| 49152  ||1141484|| || Exoo-Jajcay
+|style="background-color: #cccccc;"| 29 ||style="background-color: #cccccc;"| 49152  ||805746|| || Erskine-Tuite
 |-
-|style="background-color: #cccccc;"| 30 ||style="background-color: #cccccc;"| 65536  ||1143408|| || Exoo-Jajcay
+|style="background-color: #cccccc;"| 30 ||style="background-color: #cccccc;"| 65536  ||806736|| || Erskine-Tuite
 |-
-|style="background-color: #cccccc;"| 31 ||style="background-color: #cccccc;"| 98304  ||3649794 || ||Bray-Parker-Rowley
+|style="background-color: #cccccc;"| 31 ||style="background-color: #cccccc;"| 98304  ||1440338|| ||Erskine-Tuite
 |-
-|style="background-color: #cccccc;"| 32 ||style="background-color: #cccccc;"| 131072  ||3650304|| || Bray-Parker-Rowley
+|style="background-color: #cccccc;"| 32 ||style="background-color: #cccccc;"| 131072  ||1441440|| || Erskine-Tuite
 |}
 </center>

@@ Line 117: / Line 117: @@
 |style="background-color: #cccccc;"|12 ||style="background-color: #cccccc;"|147|| 203|| Exoo
 |-
-|style="background-color: #cccccc;"|13 ||style="background-color: #cccccc;"|174 ||240 ||Exoo
+|style="background-color: #cccccc;"|13 ||style="background-color: #cccccc;"|174 ||230 ||Exoo
 |-
 |style="background-color: #cccccc;"|14 ||style="background-color: #cccccc;"|199 ||288 ||Jørgensen

@@ Line 111: / Line 111: @@
 |style="background-color: #cccccc;"|9 ||style="background-color: #cccccc;"|86|| 96 ||Jørgensen
 |-
-|style="background-color: #cccccc;"|10 ||style="background-color: #cccccc;"|103|| 126 ||Exoo
+|style="background-color: #cccccc;"|10 ||style="background-color: #cccccc;"|103|| 124 ||Exoo
 |-
-|style="background-color: #cccccc;"|11 ||style="background-color: #cccccc;"|124 ||156|| Jørgensen
+|style="background-color: #cccccc;"|11 ||style="background-color: #cccccc;"|124 ||154|| Exoo
 |-
 |style="background-color: #cccccc;"|12 ||style="background-color: #cccccc;"|147|| 203|| Exoo
@@ Line 134: / Line 134: @@
 |}
 </center>
 ===Table 3: bounds for cages of girth 6===

@@ Line 41: / Line 41: @@
 |style="background-color: #cccccc;"| 15 ||style="background-color: #cccccc;"| 384  ||620|||| Biggs
 |-
-|style="background-color: #cccccc;"| 16 ||style="background-color: #cccccc;"| 512  ||960|| ||Exoo
+|style="background-color: #cccccc;"| 16 ||style="background-color: #cccccc;"| 512  ||936|| ||Stubbe
 |-
-|style="background-color: #cccccc;"| 17 ||style="background-color: #cccccc;"| 768  ||2176|| ||Exoo
+|style="background-color: #cccccc;"| 17 ||style="background-color: #cccccc;"| 768  ||2048|| ||Exoo
 |-
 |style="background-color: #cccccc;"| 18 ||style="background-color: #cccccc;"| 1024  ||2560|| ||Exoo

@@ Line 161: / Line 161: @@
 |style="background-color: #cccccc;"|11 ||style="background-color: #cccccc;"|224 ||240|| Wong
 |-
-|style="background-color: #cccccc;"|12 ||style="background-color: #cccccc;"|266|| 266|| Projective Plane
+|style="background-color: #cccccc;"|12 ||style="background-color: #cccccc;"|266||'''266'''|| Projective Plane
 |-
 |style="background-color: #cccccc;"|13 ||style="background-color: #cccccc;"|314 ||336|| Abreu-Funk-Labbate-Napolitano

← Older revision	Revision as of 14:39, 3 January 2019
(No difference)