An Ore-type condition for large k-factor and disjoint perfect matchings |
| |
Authors: | Hongliang Lu Bo Ning |
| |
Affiliation: | 1. School of Mathematics and Statistics, Xi'an Jiaotong University, Xi'an, China;2. Center for Applied Mathematics, Tianjin University, Tianjin, China |
| |
Abstract: | Win conjectured that a graph on vertices contains disjoint perfect matchings, if the degree sum of any two nonadjacent vertices is at least , where is even and . In this paper, we prove that Win's conjecture is true for , where is sufficiently large. To show this result, we prove a theorem on -factor in a graph under some Ore-type condition. Our main tools include Tutte's -factor theorem, the Karush-Kuhn-Tucker theorem on convex optimization and the solution to the long-standing 1-factor decomposition conjecture. |
| |
Keywords: | degree sum factorization hamiltonian graph Karush-Kuhn-Tucker condition Ore-type condition perfect matching regular graph |
|
|