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

DOI10.1016/J.EJC.2012.05.002MaRDI QIDQ449212zbMATH OpenOpenAlexFDO

Authors M. Abreu, D. Labbate, J. Sheehan

Publication date 12 September 2012

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1002.1033

zbMATH Keywords

Flower snarks

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Infinite graphs (05C63) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

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$. In cite{ADJLS} we proved that pseudo 2--factor isomorphic $k$--regular bipartite graphs exist only for $kle3$. 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 $kgeq4$. 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 Blanuv{s}a2 graphs, they are the only cyclically 4--edge--connected snarks for which each 2--factor contains only cycles of odd length.

Recommendations

• Pseudo 2-factor isomorphic regular bipartite graphs
• A counterexample to the pseudo 2-factor isomorphic graph conjecture
• A construction for a counterexample to the pseudo 2-factor isomorphic graph conjecture
• Graphs and digraphs with all 2-factors isomorphic
• Irreducible pseudo 2-factor isomorphic cubic bipartite graphs
• scientific article; zbMATH DE number 867690
• scientific article; zbMATH DE number 4101256
• On strongly regular graphs with eigenvalue 2 and their extensions
• Pseudocyclic association schemes and strongly regular graphs
• Regular bipartite graphs with all 2-factors isomorphic

Cites work

• 2-factor Hamiltonian graphs.
• Corrigendum to ``Graphs and digraphs with all 2-factors isomorphic [J. Combin. Theory Ser. B 92 (2) (2004) 395-404]
• Disconnected 2-factors in planar cubic bridgeless graphs
• Even cycles in directed graphs
• Graph theory
• Graphs and digraphs with all 2-factors isomorphic
• scientific article; zbMATH DE number 5130728 (Why is no real title available?)
• scientific article; zbMATH DE number 227006 (Why is no real title available?)
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Matching theory
• Pseudo 2-factor isomorphic regular bipartite graphs
• Regular bipartite graphs with all 2-factors isomorphic
• The Even Cycle Problem for Directed Graphs
• Tutte's edge-colouring conjecture

Cited in

(8)

• On 2-factor Hamiltonian regular bipartite graphs
• A counterexample to the pseudo 2-factor isomorphic graph conjecture
• Odd 2-factored snarks
• 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
• Generation and properties of snarks
• Graphs and digraphs with all 2-factors isomorphic

This page was built for publication: Pseudo and strongly pseudo 2-factor isomorphic regular graphs and digraphs

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