110-vertex Iofinova–Ivanov graph

Marina Evgenievna Iofinova and Alexander A. Ivanov proved in 1985 the existence of five and only five semi-symmetric cubic bipartite graphs whose automorphism groups act primitively on each partition.{{cite web|last1=Han and Lu|title=Affine primitive groups and Semisymmetric graphs|url=http://www.combinatorics.org/ojs/index.php/eljc/article/viewFile/v20i2p39/pdf|website=combinatorics.org|accessdate=12 August 2015}} The smallest has 110 vertices. The others have 126, 182, 506 and 990.{{cite web|last1=Weisstein|first1=Eric|title=Iofinova-Ivanov Graphs|url=http://mathworld.wolfram.com/Iofinova-IvanovGraphs.html|website=Wolfram MathWorld|publisher=Wolfram|accessdate=11 August 2015}} The 126-vertex Iofinova–Ivanov graph is also known as the Tutte 12-cage. According to Ivanov, during their initial work on the graph, Iofinova believed that "This work will not make us famous." By 2025, their paper would go on to be Ivanov's second most cited work, followed by their paper with Cheryl E. Praeger on Affine 2-transitive graphs, although Iofinova had died in 1999.{{cite book |last1=Ivanov |first1=Alexander A. |title=Ever-Evolving Groups: An Introduction to Modern Finite Group Theory |date=2025 |publisher=Springer Nature Switzerland |location=Cham |isbn=978-3-031-89011-6 |page=46 |edition=1st 2025}}

The Iofinova-Ivanov graph is significant as it was specifically constructed to be acted on by a symmetry group $G$ satisfying four properties. First, the graph $\backslash Omega$ can partitioned into two orbits $\backslash Omega\_1$ and $\backslash Omega\_2$ where the stabilizer of an element in one partition has an orbit length of 3 on the elements in the other partition, and vice versa. Second, no non-trival equivalence relation on the partitions are preserved by the group. Third, any permutation on the graph that preserves the aforementioned length 3 relation will preserve the partions. Finally, the group must be self-normalizing on the permutation group on $\backslash Omega$; any permutation that normalizes the group $G$ is necessarily in the group.

A group $G$ that acts on a set $\backslash Omega$ satisfying the mentioned properties must be one of five groups, up to isomorphism: $PGL\_2(11)$, $G\_2(2)$, $PGL\_2(13)$, $PSL\_2(23)$, and $\backslash text\{Aut\}(M\_\{12\})$. Here, $PGL\_2(p)$ denotes the Projective general linear group with entries in the finite field of order $p$, $PSL\_2(p)$ is the Projective special linear group again with entries in the corresponding field, while $G\_2(q)$ is the Dickson group, and $\backslash text\{Aut\}(M\_\{12\})$ is the automorphism group of the Mathieu group $M\_\{12\}$. The corresponding sets that these groups act on are graphs with 110, 126, 182, 506, and 990 vertices respectively, and the Iofinova-Ivanov graph corresponds to the smallest of these graphs.

The characteristic polynomial of the 110-vertex Iofina-Ivanov graph is $(x-3)\; x^\{20\}\; (x+3)\; (x^4-8\; x^2+11)^\{12\}\; (x^4-6\; x^2+6)^\{10\}$.

The symmetry group of the 110-vertex Iofina-Ivanov is the projective linear group PGL₂(11), with 1320 elements.{{cite book|last1=Iofinova and Ivanov|title=Investigations in Algebraic Theory of Combinatorial Objects|date=2013|publisher=Springer|page=470|isbn=9789401719728|url=https://books.google.com/books?id=NVDqCAAAQBAJ&q=Iofinova+graph&pg=PA470|accessdate=12 August 2015}}

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.{{citation | last1 = Conder | first1 = M. | author1-link = Marston Conder

| last2 = Malnič | first2 = A.

| last3 = Marušič | first3 = D. | author3-link = Dragan Marušič

| last4 = Pisanski | first4 = T. | author4-link = Tomaž Pisanski

| last5 = Potočnik | first5 = P.

| issue = 845

| location = Ljubljana

| periodical = IMFM Preprints

| publisher = Institute of Mathematics, Physics and Mechanics

| title = The Ljubljana Graph

| url = http://www.imfm.si/preprinti/PDF/00845.pdf

| volume = 40

| year = 2002}}{{citation

| last1 = Conder | first1 = Marston | author1-link = Marston Conder

| last2 = Malnič | first2 = Aleksander

| last3 = Marušič | first3 = Dragan | authorlink3 = Dragan Marušič

| last4 = Potočnik | first4 = Primož

| title = A census of semisymmetric cubic graphs on up to 768 vertices

| journal = Journal of Algebraic Combinatorics

| volume = 23 | year = 2006 | pages = 255–294

| doi = 10.1007/s10801-006-7397-3

| issue = 3| doi-access = free}}. It is only for the five Iofina-Ivanov graphs that the symmetry group acts primitively on each partition of the vertices.

{{reflist}}

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

{{DEFAULTSORT:110-vertex Iofinova-Ivanov graph}}

Category:Individual graphs

Category:Regular graphs