{"id":1755,"date":"2015-10-01T01:00:25","date_gmt":"2015-10-01T01:00:25","guid":{"rendered":"http:\/\/blogs.ams.org\/visualinsight\/?p=1755"},"modified":"2016-03-29T19:44:46","modified_gmt":"2016-03-29T19:44:46","slug":"balaban-10-cage","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/visualinsight\/2015\/10\/01\/balaban-10-cage\/","title":{"rendered":"Balaban 10-Cage"},"content":{"rendered":"
\n
\"Balaban<\/a>

Balaban 10-Cage – Koko90<\/p><\/div>\n<\/div>\n

This is the Balaban 10-cage<\/a>, the first known (3,10)-cage. An \\((r,g)\\)-cage<\/b><\/a> is graph where every vertex has \\(r\\) neighbors, the shortest cycle has length at least \\(g\\), and the number of vertices is minimal given these constraints. The Balaban 10-cage has 70 vertices, 105 edges, and a symmetry group of order 80, which does not act transitively on the nodes or edges of this graph.<\/p>\n

It is easy to see that \\((r,g)\\)-cages are uninteresting for \\(r \\lt 3\\). There exists at least one \\((3,g)\\)-cage for any \\(g \\ge 3\\). For low values \\(g\\) we have discussed many of these \\((3,g)\\)-cages already on Visual Insight<\/i>—click the links to see them:<\/p>\n

• The only (3,3)-cage is \\(K_4\\), the complete graph<\/a> on 4 vertices, having an edge between each pair of distinct vertices.<\/p>\n

\n
\"Complete<\/a>

\\(K_4\\) – Koko90<\/p><\/div>\n<\/div>\n

• The only (3,4)-cage is \\(K_{3,3}\\), the complete bipartite graph<\/a> with 3 red vertices and 3 blue vertices and an edge between each red vertex and each blue vertex.<\/p>\n

\n
\"Complete<\/a>

\\(K_{3,3}\\) – -xfi-<\/p><\/div>\n<\/div>\n

• The only (3,5)-cage is the Petersen graph<\/a>.<\/p>\n

\n
\"Petersen<\/a>

Petersen Graph – Chris Martin<\/p><\/div>\n<\/div>\n

• The only (3,6)-cage is the Heawood graph<\/a>.<\/p>\n

\n
\"Heawood<\/a>

Heawood Graph – Koko90<\/p><\/div>\n<\/div>\n

• The only (3,7)-cage is the McGee graph<\/a>.<\/p>\n

\n
\"McGee<\/a>

McGee Graph – Koko90<\/p><\/div>\n<\/div>\n

• The only (3,8)-cage is the Tutte–Coxeter graph<\/a>.<\/p>\n

\n
\"Tutte--Coxeter<\/a>

Tutte–Coxeter Graph – Koko90<\/p><\/div>\n<\/div>\n

• There are 18 nonisomorphic (3,9)-cages.<\/p>\n

• There are 3 nonisomorphic (3,10)-cages.<\/p>\n

The Balaban 10-cage first appeared here:<\/p>\n

• Alexandru T. Balaban, A trivalent graph of girth ten<\/a>, J. Combin. Theory Ser. B<\/i> 12<\/b> (1972), 1–5. <\/p>\n

Balaban was working mostly on chemistry in this phase of his life, and later wrote:<\/p>\n

\nIn my spare time, I tried to solve graph-theoretical problems, and I became intrigued by the fact that trivalent cages were known for girths 3 to 8 and 12, but there was a gap for girths 9, 10, and 11. With symmetry as a guide and with my observation on how smaller cages can be obtained from larger cages I found a trivalent graph with 70 vertices and I conjectured that it was a 10-cage, but I did not publish this result until a few years later. Only much later was it proved to be indeed the first 10-cage (two other ones were discovered later) by mathematicians using arrays of computers working for long time; a similar computational effort proved that another conjectured trivalent graph with 112 vertices to be the unique 11-cage. Both these cages are known as \u201cBalaban graphs\u201d; the Balaban 10-cage appears on the cover of the book Pearls in Graph Theory by N. Hartsfield and G. Ringel. In an international effort that included Coxeter, Frucht, Harries, and Evans along with me, we had found several nice, highly symmetric graphs with 60 vertices and girth 9, but before anything was published about them, Norman Biggs published a paper about the first 9-cage with 58 vertices. It is now known that there are eighteen 9-cages, all with low symmetry.\n<\/p><\/blockquote>\n

This is from:<\/p>\n

• Alexandru T. Balaban, Autobiographical notes: 80 years of age, 68 years of chemistry<\/a>, MATCH Commun. Math. Comput. Chem.<\/i> 66<\/b> (2011), 7–32.<\/p>\n

For more on cages, see:<\/p>\n

• Cage (graph theory)<\/a>, Wikipedia<\/i>.<\/p>\n

• Geoffrey Exoo and Robert Jajcay, Dynamic cage survey<\/a>, Electronic Journal of Combinatorics, Dynamic Survey<\/i> DS16<\/b> (2013).<\/p>\n

• Mirka Miller and Jozef Sir\u00e1n, Moore graphs and beyond: a survey of the degree\/diameter problem<\/a>, Electronic Journal of Combinatorics, Dynamic Survey<\/i> DS14<\/b> (2013).<\/p>\n

The layout for the featured picture comes from here:<\/p>\n

• T. Pisanski, M. Boben, D. Maru, A. Orbani and A. Graovac, The 10-cages and derived configurations, Discrete Mathematics<\/i> 275<\/b> (2004), 265–276.<\/p>\n

The featured picture was created by Koko90<\/a> and put on Wikicommons<\/a> under a Creative Commons Attribution-Share Alike 3.0 Unported license<\/a>. For information on the other pictures, click the links, except for:<\/p>\n

• the complete graph \\(K_4\\), which was drawn by Koko90<\/a> and put on Wikicommons<\/a> under a Creative Commons Attribution-Share Alike 3.0 Unported license<\/a>,<\/p>\n

• the complete bipartite graph \\(K_{3,3}\\), which was drawn by -xfi-<\/a> and put on Wikicommons<\/a> under a Creative Commons Attribution-Share Alike 3.0 Unported license<\/a>, and<\/p>\n

• the Petersen graph, which was drawn by Chris Martin<\/a> and placed into the public domain on Wikicommons<\/a>.<\/p>\n

\n

Visual Insight<\/i> is a place to share striking images that help explain advanced topics in mathematics. I\u2019m always looking for truly beautiful images, so if you know about one, please drop a comment here<\/a> and let me know!<\/p>\n

<\/div>","protected":false},"excerpt":{"rendered":"

This is the Balaban 10-cage<\/a>, the first known (3,10)-cage. An \\((r,g)\\)-cage<\/b><\/a> is graph where every vertex has \\(r\\) neighbors, the shortest cycle has length at least \\(g\\), and the number of vertices is maximal given these constraints. <\/p>\n

<\/div>\n","protected":false},"author":66,"featured_media":1756,"comment_status":"open","ping_status":"closed","sticky":true,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[21,22,2],"tags":[],"class_list":["post-1755","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-combinatorics","category-graphs","category-images-library"],"jetpack_featured_media_url":"https:\/\/blogs.ams.org\/visualinsight\/files\/2015\/07\/balaban_10-cage.png","jetpack_shortlink":"https:\/\/wp.me\/p42Vmc-sj","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/1755","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/users\/66"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/comments?post=1755"}],"version-history":[{"count":34,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/1755\/revisions"}],"predecessor-version":[{"id":2500,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/1755\/revisions\/2500"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/media\/1756"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/media?parent=1755"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/categories?post=1755"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/tags?post=1755"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}