On 2-factors containing 1-factors in bipartite graphs (Q1292826)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On 2-factors containing 1-factors in bipartite graphs |
scientific article |
Statements
On 2-factors containing 1-factors in bipartite graphs (English)
0 references
5 December 1999
0 references
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.
0 references
bipartite graphs
0 references
\(2\)-factors
0 references
perfect matching
0 references
degree
0 references
hamiltonian cycle
0 references