A bipartite graph is pseudo 2-factor isomorphic if the number of circuits in each 2-factor of the graph is always even or always odd. We proved (Abreu et al., J Comb Theory B 98:432–442, 2008) that the only essentially 4-edge-connected pseudo 2-factor isomorphic cubic bipartite graph of girth 4 is$ K_{3,3}$, and conjectured (Abreu et al., 2008, Conjecture 3.6) that the only essentially 4-edge-connected cubic bipartite graphs are $K_{3,3}$, the Heawood graph and the Pappus graph. There exists a characterization of symmetric configurations $n _3$ due to Martinetti (1886) in which all symmetric configurations $n_3$ can be obtained from an infinite set of so called irreducible configurations (Martinetti, Annali di Matematica Pura ed Applicata II 15:1–26, 1888). The list of irreducible configurations has been completed by Boben (Discret Math 307:331–344, 2007) in terms of their irreducible Levi graphs. In this paper we characterize irreducible pseudo 2-factor isomorphic cubic bipartite graphs proving that the only pseudo 2-factor isomorphic irreducible Levi graphs are the Heawood and Pappus graphs. Moreover, the obtained characterization allows us to partially prove the above Conjecture.

Irreducible pseudo 2-factor isomorphic cubic bipartite graphs

ABREU, Marien;LABBATE, Domenico;
2012-01-01

Abstract

A bipartite graph is pseudo 2-factor isomorphic if the number of circuits in each 2-factor of the graph is always even or always odd. We proved (Abreu et al., J Comb Theory B 98:432–442, 2008) that the only essentially 4-edge-connected pseudo 2-factor isomorphic cubic bipartite graph of girth 4 is$ K_{3,3}$, and conjectured (Abreu et al., 2008, Conjecture 3.6) that the only essentially 4-edge-connected cubic bipartite graphs are $K_{3,3}$, the Heawood graph and the Pappus graph. There exists a characterization of symmetric configurations $n _3$ due to Martinetti (1886) in which all symmetric configurations $n_3$ can be obtained from an infinite set of so called irreducible configurations (Martinetti, Annali di Matematica Pura ed Applicata II 15:1–26, 1888). The list of irreducible configurations has been completed by Boben (Discret Math 307:331–344, 2007) in terms of their irreducible Levi graphs. In this paper we characterize irreducible pseudo 2-factor isomorphic cubic bipartite graphs proving that the only pseudo 2-factor isomorphic irreducible Levi graphs are the Heawood and Pappus graphs. Moreover, the obtained characterization allows us to partially prove the above Conjecture.
2012
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: https://hdl.handle.net/11563/9238
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact