# 110-vertex Iofinova-Ivanov graph

110-vertex Iofinova-Ivanov graph | |
---|---|

Vertices | 110 |

Edges | 165 |

Radius | 7 |

Diameter | 7 |

Girth | 10 |

Automorphisms |
1320 (PGL_{2}(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.

## Contents

## Properties[edit]

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.

### Coloring[edit]

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.

### Algebraic properties[edit]

The characteristic polynomial of the 110-vertex Iofina-Ivanov graph is .
The symmetry group of the 110-vertex Iofina-Ivanov is the projective linear group PGL_{2}(11), with 1320 elements.^{[3]}

## Semi-symmetry[edit]

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.

## References[edit]

**^**Han and Lu. "Affine primitive groups and Semisymmetric graphs".*combinatorics.org*. Retrieved 12 August 2015.**^**Weisstein, Eric. "Iofinova-Ivanov Graphs".*Wolfram MathWorld*. Wolfram. Retrieved 11 August 2015.**^**Iofinova and Ivanov (2013).*Investigations in Algebraic Theory of Combinatorial Objects*. Springer. p. 470. Retrieved 12 August 2015.**^**Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; Potočnik, P. (2002), "The Ljubljana Graph" (PDF),*IMFM Preprints*, Ljubljana: Institute of Mathematics, Physics and Mechanics,**40**(845)**^**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**(3): 255–294, doi:10.1007/s10801-006-7397-3.

## Bibliography[edit]

- 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.