Tutte 12-cage
| Tutte 12-cage | |
|---|---|
 The Tutte 12-cage | |
| Named after | W. T. Tutte |
| Vertices | 126 |
| Edges | 189 |
| Radius | 6 |
| Diameter | 6 |
| Girth | 12 |
| Automorphisms | 12096 |
| Chromatic number | 2 |
| Chromatic index | 3 |
| Properties | Cubic Cage Hamiltonian Semi-symmetric Bipartite |
| Table of graphs and parameters | |
In the mathematical field of graph theory, the Tutte 12-cage or Benson graph[1] is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte.[2]
The Tutte 12-cage is the unique (3-12)-cage (sequence A052453 in the OEIS). It was discovered by C. T. Benson in 1966.[3] It has chromatic number 2 (bipartite), chromatic index 3, girth 12 (as a 12-cage) and diameter 6. Its crossing number is 170 and has been conjectured to be the smallest cubic graph with this crossing number.[4][5]
Contents
1 Construction
2 Algebraic properties
3 Gallery
4 References
Construction
The Tutte 12-cage is a cubic Hamiltonian graph and can be defined by the LCF notation [17, 27, –13, –59, –35, 35, –11, 13, –53, 53, –27, 21, 57, 11, –21, –57, 59, –17]7.[6]
There are, up to isomorphism, precisely two generalized hexagons of order (2,2) as proved by Cohen and Tits. They are the split Cayley hexagon H(2) and its point-line dual. Clearly both of them have the same incidence graph, which is in fact isomorphic to the Tutte 12-cage.[1]
The Balaban 11-cage can be constructed by excision from the Tutte 12-cage by removing a small subtree and suppressing the resulting vertices of degree two.[7]
Algebraic properties
The automorphism group of the Tutte 12-cage is of order 12,096 and is a semi-direct product of the projective special unitary group PSU(3,3) with the cyclic group Z/2Z.[1] It acts transitively on its edges but not on its vertices, making it a semi-symmetric graph, a regular graph that is edge-transitive but not vertex-transitive. In fact, the automorphism group of the Tutte 12-cage preserves the bipartite parts and acts primitively on each part. Such graphs are called bi-primitive graphs and only five cubic bi-primitive graphs exist; they are named the Iofinova-Ivanov graphs and are of order 110, 126, 182, 506 and 990.[8]
All the cubic semi-symmetric graphs on up to 768 vertices are known. According to Conder, Malnič, Marušič and Potočnik, the Tutte 12-cage is the unique cubic semi-symmetric graph on 126 vertices and is the fifth smallest possible cubic semi-symmetric graph after the Gray graph, the Iofinova–Ivanov graph on 110 vertices, the Ljubljana graph and a graph on 120 vertices with girth 8.[9]
The characteristic polynomial of the Tutte 12-cage is
- (x−3)x28(x+3)(x2−6)21(x2−2)27. {displaystyle (x-3)x^{28}(x+3)(x^{2}-6)^{21}(x^{2}-2)^{27}. }
It is the only graph with this characteristic polynomial; therefore, the 12-cage is determined by its spectrum.
Gallery
The chromatic number of the Tutte 12-cage is 2.
The chromatic index of the Tutte 12-cage is 3.
References
^ abc Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15 (2008).
^ Weisstein, Eric W. "Tutte 12-cage". MathWorld..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
^ Benson, C. T. "Minimal Regular Graphs of Girth 8 and 12." Can. J. Math. 18, 1091–1094, 1966.
^ Exoo, G. "Rectilinear Drawings of Famous Graphs".
^ Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009.
^ Polster, B. A Geometrical Picture Book. New York: Springer, p. 179, 1998.
^ Balaban, A. T. "Trivalent Graphs of Girth Nine and Eleven and Relationships Among the Cages." Rev. Roumaine Math 18, 1033–1043, 1973.
^ Iofinova, M. E. and Ivanov, A. A. "Bi-Primitive Cubic Graphs." In Investigations in the Algebraic Theory of Combinatorial Objects. pp. 123–134, 2002. (Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moscow, pp. 137–152, 1985.)
^ Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Potočnik, Primož (2006), "A census of semisymmetric cubic graphs on up to 768 vertices", Journal of Algebraic Combinatorics, 23: 255–294, doi:10.1007/s10801-006-7397-3.
