A graph G admitting a 2-factor is pseudo 2-factor isomorphic if the parity of the number of cycles in all its 2-factors is the same. In [M. Abreu, A.A. Diwan, B. Jackson, D. Labbate and J. Sheehan. Pseudo 2-factor isomorphic regular bipartite graphs. Journal of Combinatorial Theory, Series B, 98(2) (2008), 432-444.] some of the authors of this note gave a partial characterization of pseudo 2-factor isomorphic bipartite cubic graphs and conjectured that K_{3,3}, the Heawood graph and the Pappus graph are the only essentially 4-edge-connected ones. In [J. Goedgebeur. A counterexample to the pseudo 2-factor isomorphic graph conjecture. Discr. Applied Math., 193 (2015), 57-60.] Jan Goedgebeur computationally found a graph $\mathscr{G}$ on 30 vertices which is pseudo 2-factor isomorphic cubic and bipartite, essentially 4-edge-connected and cyclically 6-edge-connected, thus refuting the above conjecture. In this note, we describe how such a graph can be constructed from the Heawood graph and the generalised Petersen graph GP(8,3), which are the Levi graphs of the Fano 7_3 configuration and the M\"obius-Kantor 8_3 configuration, respectively. Such a description of $\mathscr{G}$ allows us to understand its automorphism group, which has order 144, using both a geometrical and a graph theoretical approach simultaneously. Moreover we illustrate the uniqueness of this graph.
A construction for a counterexample to the pseudo 2-factor isomorphic graph conjecture
Marien Abreu
;Martin Funk;Domenico Labbate;
2023-01-01
Abstract
A graph G admitting a 2-factor is pseudo 2-factor isomorphic if the parity of the number of cycles in all its 2-factors is the same. In [M. Abreu, A.A. Diwan, B. Jackson, D. Labbate and J. Sheehan. Pseudo 2-factor isomorphic regular bipartite graphs. Journal of Combinatorial Theory, Series B, 98(2) (2008), 432-444.] some of the authors of this note gave a partial characterization of pseudo 2-factor isomorphic bipartite cubic graphs and conjectured that K_{3,3}, the Heawood graph and the Pappus graph are the only essentially 4-edge-connected ones. In [J. Goedgebeur. A counterexample to the pseudo 2-factor isomorphic graph conjecture. Discr. Applied Math., 193 (2015), 57-60.] Jan Goedgebeur computationally found a graph $\mathscr{G}$ on 30 vertices which is pseudo 2-factor isomorphic cubic and bipartite, essentially 4-edge-connected and cyclically 6-edge-connected, thus refuting the above conjecture. In this note, we describe how such a graph can be constructed from the Heawood graph and the generalised Petersen graph GP(8,3), which are the Levi graphs of the Fano 7_3 configuration and the M\"obius-Kantor 8_3 configuration, respectively. Such a description of $\mathscr{G}$ allows us to understand its automorphism group, which has order 144, using both a geometrical and a graph theoretical approach simultaneously. Moreover we illustrate the uniqueness of this graph.File | Dimensione | Formato | |
---|---|---|---|
DAM328_2023.pdf
solo utenti autorizzati
Tipologia:
Pdf editoriale
Licenza:
Versione editoriale
Dimensione
606.99 kB
Formato
Adobe PDF
|
606.99 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.