Restricted 2-factors in Bipartite Graphs
The k-restricted 2-factor problem is that of finding a spanning subgraph consisting of disjoint cycles with no cycle of length less than or equal to k. It is a generalization of the well known Hamilton cycle problem and is equivalent to this problem when n/2<=k<s=n-1. This paper considers necessary and sufficient conditions, algorithms, and polyhedral conditions for 2-factors in bipartite graphs and restricted 2-factors in bipartite graphs. We introduce a generalization of the necessary and sufficient condition for 4-restricted 2-factors in bipartite graphs to 2k-restricted 2-factors in bipartite graphs of a particular form.
This work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/17432
Citable link to this pagehttps://hdl.handle.net/1911/101962
MetadataShow full item record
- CAAM Technical Reports