110-vertex Iofinova–Ivanov graph

110-vertex Iofinova–Ivanov graph
Vertices	110
Edges	165
Radius	7
Diameter	7
Girth	10
Automorphisms	1320 (PGL2(11))
Chromatic number	2
Chromatic index	3
Properties	semi-symmetric bipartite cubic Hamiltonian
Table of graphs and parameters

The 110-vertex Iofinova–Ivanov graph is, in graph theory, a semi-symmetric cubic graph with 110 vertices and 165 edges.

Iofinova and Ivanov proved in 1985 the existence of five and only five semi-symmetric cubic bipartite graphs whose automorphism groups act primitively on each partition.^[1] The smallest has 110 vertices. The others have 126, 182, 506 and 990.^[2] The 126-vertex Iofinova–Ivanov graph is also known as the Tutte 12-cage.

The diameter of the 110-vertex Iofinova–Ivanov graph, the greatest distance between any pair of vertices, is 7. Its radius is likewise 7. Its girth is 10.

It is 3-connected and 3-edge-connected: to make it disconnected at least three edges, or at least three vertices, must be removed.

The chromatic number of the 110-vertex Iofina-Ivanov graph is 2: its vertices can be 2-colored so that no two vertices of the same color are joined by an edge. Its chromatic index is 3: its edges can be 3-colored so that no two edges of the same color met at a vertex.

The characteristic polynomial of the 110-vertex Iofina-Ivanov graph is ${\displaystyle (x-3)x^{20}(x+3)(x^{4}-8x^{2}+11)^{12}(x^{4}-6x^{2}+6)^{10}}$. The symmetry group of the 110-vertex Iofina-Ivanov is the projective linear group PGL₂(11), with 1320 elements.^[3]

Few graphs show semi-symmetry: most edge-transitive graphs are also vertex-transitive. The smallest semi-symmetric graph is the Folkman graph, with 20 vertices, which is 4-regular. The three smallest cubic semi-symmetric graphs are the Gray graph, with 54 vertices, this the smallest of the Iofina-Ivanov graphs with 110, and the Ljubljana graph with 112.^[4][5] It is only for the five Iofina-Ivanov graphs that the symmetry group acts primitively on each partition of the vertices.

• 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.)
• Ivanov, A. A. Computation of Lengths of Orbits of a Subgroup in a Transitive Permutation Group. In Methods for Complex System Studies. Moscow: VNIISI, pp. 3–7, 1983.
• Ivanov, A. V. On Edge But Not Vertex Transitive Regular Graphs. In Combinatorial Design Theory (Ed. C. J. Colbourn and R. Mathon). Amsterdam, Netherlands: North-Holland, pp. 273–285, 1987.