Pseudo 2-factor isomorphic graphs

Home CAAGT Authors Jan Goedgebeur

Pseudo 2-factor isomorphic graphs This page contains supplementary material for the paper: J. Goedgebeur, A counterexample to the pseudo 2-factor isomorphic graph conjecture, Discrete Applied Mathematics, 193:57-60, 2015 (arXiv | DOI). 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. In [1] 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. However using a computer search we showed that this conjecture is false by constructing a counterexample with 30 vertices. The computer search also showed that this is the only counterexample up to at least 40 vertices. The adjacency list of the counterexample can be found here and it can also be downloaded in graph6 format here. This cubic bipartite graph has cyclic edge-connectivity 6 and has 312 2-factors and the cycle sizes of its 2-factors are: (6,6,18), (6,10,14), (10,10,10) and (30). The list of all perfect matchings of the graph can be found here and the list of all corresponding 2-factors here. This graph can also be obtained from House of Graphs [2] by searching for the keywords: "pseudo 2-factor isomorphic * counterexample" where it can be downloaded and several of its invariants can be inspected. References [1] 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):432–44, 2008. [2] K. Coolsaet, S. D'hondt and J. Goedgebeur, House of Graphs 2.0: a database of interesting graphs and more, Discrete Applied Mathematics, 325:97-107, 2023. Available at https://houseofgraphs.org