On 2-factors containing 1-factors in bipartite graphs

DOI10.1016/S0012-365X(99)90061-4MaRDI QIDQ1292826zbMATH OpenOpenAlexFDO

Authors Guantao Chen, Michael Jacobson, Ronald Gould

Publication date 5 December 1999

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)90061-4

zbMATH Keywords

\(2\)-factorsbipartite graphsdegreehamiltonian cycleperfect matching

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

For a fixed positive integer \(k\), it is shown that if \(G\) is a balanced bipartite graph of order \(2n\) with \(n \geq 9k\), and \(\delta (G) \geq (n + 2)/2\), then for any perfect matching \(M\) of \(G\), there is a \(2\)-factor \(F\) with exactly \(k\) cycles that contains \(M\). This generalizes a result of Las Vergnas in his doctoral dissertation that implies the existence of a hamiltonian cycle containing a perfect matching under the same minimum degree condition.

Recommendations

• scientific article; zbMATH DE number 2147779
• On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs
• A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs
• On 2-factors with cycles containing specified vertices in a bipartite graph
• On 2-factors of a bipartite graph

Cites work

• Cycles containing matchings and pairwise compatible euler tours
• Cycles in 2-factors of balanced bipartite graphs
• Degree conditions for 2-factors
• scientific article; zbMATH DE number 3722690 (Why is no real title available?)
• On Hamiltonian bipartite graphs
• Proof of a conjecture of Haeggkvist on cycles and independent edges
• Some Theorems on Abstract Graphs

Cited in

(14)

• On 2-factors with cycles containing specified edges in a bipartite graph
• A look at cycles containing specified elements of a graph
• Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
• On degree sum conditions for directed path-factors with a specified number of paths
• A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs
• On 2-factors with prescribed properties in a bipartite graph
• Two sufficient conditions for a 2-factor in a bipartite graph
• Extensions to 2-factors in bipartite graphs
• Proof of a conjecture on cycles in a bipartite graph
• On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs
• scientific article; zbMATH DE number 2147779 (Why is no real title available?)
• Bipartite multigraphs with 1‐factors containing specified edges
• Disjoint Cycles in a Digraph with Partial Degree
• Vertex-disjoint quadrilaterals containing specified edges in a bipartite graph

This page was built for publication: On 2-factors containing 1-factors in bipartite graphs

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