An Ore‐type condition for large k‐factor and disjoint perfect matchings. Issue 3 (25th November 2019)

• Record Type: Journal Article
• Authors: Lu, Hongliang; Ning, Bo
• Is Part Of: Journal of graph theory. Volume 94:Issue 3(2020)
• Page Start: 307
• Page End: 319
• Publication Date: 2019-11-25
• Subjects: degree sum -- factorization -- hamiltonian graph -- Karush‐Kuhn‐Tucker condition -- Ore‐type condition -- perfect matching -- regular graph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22522
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: Win conjectured that a graph G on n vertices contains k disjoint perfect matchings, if the degree sum of any two nonadjacent vertices is at least n + k − 2, where n is even and n ≥ k + 2 . In this paper, we prove that Win's conjecture is true for k ≥ n ∕ 2, where n is sufficiently large. To show this result, we prove a theorem on k ‐factor in a graph under some Ore‐type condition. Our main tools include Tutte's k ‐factor theorem, the Karush‐Kuhn‐Tucker theorem on convex optimization and the solution to the long‐standing 1‐factor decomposition conjecture.