Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418846 | Discrete Applied Mathematics | 2015 | 4 Pages |
A graph GG 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 GG. Abreu et al. conjectured that K3,3K3,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., 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 GG is 2-factor hamiltonian if all 2-factors of GG are hamiltonian cycles. Funk et al. conjectured that every 2-factor hamiltonian cubic bipartite graph can be obtained from K3,3K3,3 and the Heawood graph by applying repeated star products (Funk et al., 2003, Conjecture 3.2). We verify that this conjecture holds up to at least 40 vertices.