On 2-factors containing 1-factors in bipartite graphs (Q1292826)

From MaRDI portal





scientific article; zbMATH DE number 1322011
Language Label Description Also known as
default for all languages
No label defined
    English
    On 2-factors containing 1-factors in bipartite graphs
    scientific article; zbMATH DE number 1322011

      Statements

      On 2-factors containing 1-factors in bipartite graphs (English)
      0 references
      0 references
      0 references
      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
      0 references
      bipartite graphs
      0 references
      \(2\)-factors
      0 references
      perfect matching
      0 references
      degree
      0 references
      hamiltonian cycle
      0 references

      Identifiers