Extensions to 2-factors in bipartite graphs

MaRDI QIDQ396808zbMATH OpenFDO

Authors Jennifer Vandenbussche, Douglas B. West

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p11

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

2-factorbipartite graphhypercubematchingOre-Ryser theorem

Mathematics Subject Classification ID

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

Review text

Summary: A graph is \(d\)-bounded if its maximum degree is at most \(d\). We apply the Ore-Ryser Theorem on \(f\)-factors in bipartite graphs to obtain conditions for the extension of a 2-bounded subgraph to a 2-factor in a bipartite graph. As consequences, we prove that every matching in the 5-dimensional hypercube extends to a 2-factor, and we obtain conditions for this property in general regular bipartite graphs. For example, to show that every matching in a regular \(n\)-vertex bipartite graph extends to a 2-factor, it suffices to show that all matchings with fewer than \(n/3\) edges extend to 2-factors.

Recommendations

• On 2-factors of a bipartite graph
• scientific article; zbMATH DE number 2147779
• On 2-factors containing 1-factors in bipartite graphs
• On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs
• Factors of bi-regular bipartite graphs

Cites work

• Circuits through specified edges
• Factors and factorizations of graphs. Proof techniques in factor theory
• Flows in infinite graphs
• Graph factors
• Graphs and Subgraphs
• Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $
• HAMILTONIAN CYCLES THROUGH MATCHINGS
• Hamiltonian Cycles with Prescribed Edges in Hypercubes
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3722690 (Why is no real title available?)
• scientific article; zbMATH DE number 888853 (Why is no real title available?)
• scientific article; zbMATH DE number 2199618 (Why is no real title available?)
• Linear forests and ordered cycles
• Long cycles through a linear forest
• Matching Extendability in Hypercubes
• Matching graphs of hypercubes and complete bipartite graphs
• Matching, Euler tours and the Chinese postman
• Minimum degree of bipartite graphs and the existence of k-factors
• On diagnosability of large fault sets in regular topology-based computer systems
• Perfect matchings extend to Hamilton cycles in hypercubes
• Proof of a conjecture of Haeggkvist on cycles and independent edges

Cited in

(9)

• Perfect matchings extend to two or more Hamiltonian cycles in hypercubes
• Towards a problem of Ruskey and Savage on matching extendability
• Minimal graphs for 2-factor extension
• Two sufficient conditions for a 2-factor in a bipartite graph
• Proper orientations and proper chromatic number
• Matchings in hypercubes extend to long cycles
• On Tuza's conjecture in dense graphs
• Matchings in hypercubes extend to long cycles
• Matchings with five directions in hypercubes extend to Hamilton cycles and paths with prescribed ends

This page was built for publication: Extensions to 2-factors in bipartite graphs

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