Extensions to $2$-Factors in Bipartite Graphs

  • Jennifer Vandenbussche
  • Douglas B. West
Keywords: matching, 2-factor, hypercube, bipartite graph, Ore-Ryser Theorem

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.
Published
2013-08-02
Article Number
P11