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;
2022

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 in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11563/158286
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact