- Title
- On the number of disjoint perfect matchings of regular graphs with given edge connectivity
- Creator
- Lu, Hongliang; Lin, Yuqing
- Relation
- Discrete Mathematics Vol. 340, Issue 3, p. 305-310
- Publisher Link
- http://dx.doi.org/10.1016/j.disc.2016.09.002
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2017
- Description
- The problem of how many edge disjoint perfect matchings are there in a regular graph has attracted considerable interest. Most of the work focus on the case where the degree is large, roughly speaking, equal to half of the total number of the vertices in the graph. In this paper, we look at the case where the degree is smaller. Let n,k,m be three positive integers such that k=⎣(n - 1)/2⎦ and m≤k, we show that every 2k-regular m-edge-connected graph with 2n vertices contains at least m edge-disjoint perfect matchings, and the condition on edge connectivity is sharp.
- Subject
- edge disjoint perfect matching; 1-factorization conjecture
- Identifier
- http://hdl.handle.net/1959.13/1354613
- Identifier
- uon:31313
- Identifier
- ISSN:0012-365X
- Language
- eng
- Reviewed
- Hits: 5417
- Visitors: 2426
- Downloads: 1
Thumbnail | File | Description | Size | Format |
---|