A counterexample to the pseudo 2-factor isomorphic graph conjecture

DOI10.1016/J.DAM.2015.04.021MaRDI QIDQ2354717zbMATH OpenOpenAlexWikidataFDO

Authors Jan Goedgebeur

Publication date 24 July 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.3350, https://lirias.kuleuven.be/handle/123456789/681523

zbMATH Keywords

2-factorbipartite graphcomputationcounterexamplecubic graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: A graph $G$ is pseudo 2-factor isomorphic if the parity of the number of cycles in a 2-factor is the same for all 2-factors of $G$. Abreu et al. conjectured that $K_{3,3}$, the Heawood graph and the Pappus graph are the only essentially 4-edge-connected pseudo 2-factor isomorphic cubic bipartite graphs (Abreu et al., Journal of Combinatorial Theory, Series B, 2008, Conjecture 3.6). Using a computer search we show that this conjecture is false by constructing a counterexample with 30 vertices. We also show that this is the only counterexample up to at least 40 vertices. A graph $G$ is 2-factor hamiltonian if all 2-factors of $G$ are hamiltonian cycles. Funk et al. conjectured that every 2-factor hamiltonian cubic bipartite graph can be obtained from $K_{3,3}$ and the Heawood graph by applying repeated star products (Funk et al., Journal of Combinatorial Theory, Series B, 2003, Conjecture 3.2). We verify that this conjecture holds up to at least 40 vertices.

Recommendations

• A construction for a counterexample to the pseudo 2-factor isomorphic graph conjecture
• Pseudo 2-factor isomorphic regular bipartite graphs
• Pseudo and strongly pseudo 2-factor isomorphic regular graphs and digraphs
• Irreducible pseudo 2-factor isomorphic cubic bipartite graphs
• 2-factor Hamiltonian graphs.

Cites work

• 2-factor Hamiltonian graphs.
• A counterexample to the pseudo 2-factor isomorphic graph conjecture
• Characterizing minimally 1-factorable r-regular bipartite graphs
• Fast generation of cubic graphs
• Fast generation of regular graphs and construction of cages
• Generation and properties of snarks
• Generation of cubic graphs
• House of Graphs: a database of interesting graphs
• Irreducible pseudo 2-factor isomorphic cubic bipartite graphs
• On 3-cut reductions of minimally 1-factorable cubic bigraphs
• Pseudo 2-factor isomorphic regular bipartite graphs

Cited in

(7)

• A counterexample to the pseudo 2-factor isomorphic graph conjecture
• Pseudo 2-factor isomorphic regular bipartite graphs
• A construction for a counterexample to the pseudo 2-factor isomorphic graph conjecture
• Irreducible pseudo 2-factor isomorphic cubic bipartite graphs
• Pseudo and strongly pseudo 2-factor isomorphic regular graphs and digraphs
• Cubic graphs having only k-cycles in each 2-factor
• The Gray graph is pseudo 2-factor isomorphic

Describes a project that uses

Uses Software

• House of Graphs
• GENREG
• snarkhunter

This page was built for publication: A counterexample to the pseudo 2-factor isomorphic graph conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354717)