Tutte 12-cage

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]

Tutte 12-cage
The Tutte 12-cage
Named afterW. T. Tutte
Vertices126
Edges189
Radius6
Diameter6
Girth12
Automorphisms12096
Chromatic number2
Chromatic index3
PropertiesCubic
Cage
Hamiltonian
Semi-symmetric
Bipartite
Table of graphs and parameters

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]

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

It is the only graph with this characteristic polynomial; therefore, the 12-cage is determined by its spectrum.

References
  1. Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15 (2008).
  2. Weisstein, Eric W. "Tutte 12-cage". MathWorld.
  3. Benson, C. T. "Minimal Regular Graphs of Girth 8 and 12." Can. J. Math. 18, 1091–1094, 1966.
  4. Exoo, G. "Rectilinear Drawings of Famous Graphs".
  5. Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009.
  6. Polster, B. A Geometrical Picture Book. New York: Springer, p. 179, 1998.
  7. Balaban, A. T. "Trivalent Graphs of Girth Nine and Eleven and Relationships Among the Cages." Rev. Roumaine Math 18, 1033–1043, 1973.
  8. 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.)
  9. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.