Abstract
In this paper we study tight lower bounds on the size of a maximum matching in a regular graph. For k ≥3, let G be a connected k-regular graph of order n and let α′(G) be the size of a maximum matching in G. We show that if k is even, then α′(G) ≥ min {(k2 + 4/k2 + k + 2) × n/2, n-1/2}, while if k is odd, then α′(G) ≥ (k3-k2-2)n - 2k + 2/2(k3-3k). We show that both bounds are tight.
Original language | English |
---|---|
Pages (from-to) | 647-657 |
Number of pages | 11 |
Journal | Graphs and Combinatorics |
Volume | 23 |
Issue number | 6 |
DOIs | |
Publication status | Published - Dec 2007 |
Externally published | Yes |
Keywords
- Lower bounds
- Matching number
- Regular graph
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics