| 110-vertex Iofinova–Ivanov graph | |
| Vertices: | 110 |
| Edges: | 165 |
| Automorphisms: | 1320 (PGL2(11)) |
| Radius: | 7 |
| Diameter: | 7 |
| Girth: | 10 |
| Chromatic Number: | 2 |
| Chromatic Index: | 3 |
| Properties: | semi-symmetric bipartite cubic Hamiltonian |
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
(x-3)x20(x+3)(x4-8x2+11)12(x4-6x2+6)10
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] It is only for the five Iofina-Ivanov graphs that the symmetry group acts primitively on each partition of the vertices.