Extensions to $2$-Factors in Bipartite Graphs

Jennifer Vandenbussche, Douglas B. West

Abstract


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.

Keywords


matching; 2-factor; hypercube; bipartite graph; Ore-Ryser Theorem

Full Text: PDF