The Balaban 11-cage is the unique (3,11)-cage. It was discovered by Balaban in 1973.[2] The uniqueness was proved by Brendan McKay and Wendy Myrvold in 2003.[3]
The Balaban 11-cage is a Hamiltonian graph and can be constructed by excision from the Tutte 12-cage by removing a small subtree and suppressing the resulting vertices of degree two.[4]
^Balaban, Alexandru T., Trivalent graphs of girth nine and eleven, and relationships among cages, Revue Roumaine de Mathématiques Pures et Appliquées 18 (1973), 1033-1043. MR0327574
^P. Eades, J. Marks, P. Mutzel, S. North. "Graph-Drawing Contest Report", TR98-16, December 1998, Mitsubishi Electric Research Laboratories.
References
Heal, Maher (2016), "A Quadratic Programming Formulation to Find the Maximum Independent Set of Any Graph", The 2016 International Conference on Computational Science and Computational Intelligence, Las Vegas: IEEE Computer Society
May 04, 2023
balaban, cage, mathematical, field, graph, theory, balaban, cage, regular, graph, with, vertices, edges, named, after, alexandru, balaban, named, afteralexandru, balabanvertices112edges168radius6diameter8girth11automorphisms64chromatic, number3chromatic, index. In the mathematical field of graph theory the Balaban 11 cage or Balaban 3 11 cage is a 3 regular graph with 112 vertices and 168 edges named after Alexandru T Balaban 1 Balaban 11 cageThe Balaban 11 cageNamed afterAlexandru T BalabanVertices112Edges168Radius6Diameter8Girth11Automorphisms64Chromatic number3Chromatic index3PropertiesCubicCageHamiltonianTable of graphs and parametersThe Balaban 11 cage is the unique 3 11 cage It was discovered by Balaban in 1973 2 The uniqueness was proved by Brendan McKay and Wendy Myrvold in 2003 3 The Balaban 11 cage is a Hamiltonian graph and can be constructed by excision from the Tutte 12 cage by removing a small subtree and suppressing the resulting vertices of degree two 4 It has independence number 52 5 chromatic number 3 chromatic index 3 radius 6 diameter 8 and girth 11 It is also a 3 vertex connected graph and a 3 edge connected graph The characteristic polynomial of the Balaban 11 cage is x 3 x 12 x 2 6 5 x 2 2 12 x 3 x 2 4 x 2 2 displaystyle x 3 x 12 x 2 6 5 x 2 2 12 x 3 x 2 4x 2 2 cdot x 3 x 2 6 x 2 x 4 x 3 6 x 2 4 x 4 4 displaystyle cdot x 3 x 2 6x 2 x 4 x 3 6x 2 4x 4 4 cdot x 5 x 4 8 x 3 6 x 2 12 x 4 8 displaystyle cdot x 5 x 4 8x 3 6x 2 12x 4 8 The automorphism group of the Balaban 11 cage is of order 64 4 Gallery Edit The chromatic number of the Balaban 11 cage is 3 The chromatic index of the Balaban 11 cage is 3 Alternative drawing of the Balaban 11 cage 6 References Edit Weisstein Eric W Balaban 11 Cage MathWorld Balaban Alexandru T Trivalent graphs of girth nine and eleven and relationships among cages Revue Roumaine de Mathematiques Pures et Appliquees 18 1973 1033 1043 MR0327574 Weisstein Eric W Cage Graph MathWorld a b Geoffrey Exoo amp Robert Jajcay Dynamic cage survey Electr J Combin 15 2008 Heal 2016 P Eades J Marks P Mutzel S North Graph Drawing Contest Report TR98 16 December 1998 Mitsubishi Electric Research Laboratories References EditHeal Maher 2016 A Quadratic Programming Formulation to Find the Maximum Independent Set of Any Graph The 2016 International Conference on Computational Science and Computational Intelligence Las Vegas IEEE Computer Society Retrieved from https en wikipedia org w index php title Balaban 11 cage amp oldid 1088425995, wikipedia, wiki, book, books, library,
