Tight lower bounds on the size of a maximum matching in a regular graph

Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review

44 Citations (Scopus)

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 languageEnglish
Pages (from-to)647-657
Number of pages11
JournalGraphs and Combinatorics
Volume23
Issue number6
DOIs
Publication statusPublished - Dec 2007
Externally publishedYes

Keywords

  • Lower bounds
  • Matching number
  • Regular graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Tight lower bounds on the size of a maximum matching in a regular graph'. Together they form a unique fingerprint.

Cite this