Pseudo and strongly pseudo 2-factor isomorphic regular graphs and digraphs

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 Abreu et al. (2008) [3] we proved that pseudo 2-factor isomorphic k-regular bipartite graphs exist only for k <= 3. In this paper we generalize this result for regular graphs which are not necessarily bipartite. We also introduce strongly pseudo 2-factor isomorphic graphs and we prove that pseudo and strongly pseudo 2-factor isomorphic 2k-regular graphs and k-regular digraphs do not exist for k >= 4. Moreover, we present constructions of infinite families of regular graphs in these classes. In particular we show that the family of Flower snarks is strongly pseudo 2-factor isomorphic but not 2-factor isomorphic and we conjecture that, together with the Petersen and the Blanusa2 graphs, they are the only cyclically 4-edge-connected snarks for which each 2-factor contains only cycles of odd length. (C) 2012 Elsevier Ltd. All rights reserved.