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

Michael A. Henning; Anders Yeo

doi:10.1007/s00373-007-0757-5

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

Michael A. Henning, Anders Yeo

Research output: Contribution to journal › Article › peer-review

47 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 {(k² + 4/k² + k + 2) × n/2, n-1/2}, while if k is odd, then α′(G) ≥ (k³-k²-2)n - 2k + 2/2(k³-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	https://doi.org/10.1007/s00373-007-0757-5
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

Access to Document

10.1007/s00373-007-0757-5

Cite this

@article{72346742f11740cb8a42463b3c1363d6,

title = "Tight lower bounds on the size of a maximum matching in a regular graph",

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.",

keywords = "Lower bounds, Matching number, Regular graph",

author = "Henning, \{Michael A.\} and Anders Yeo",

year = "2007",

month = dec,

doi = "10.1007/s00373-007-0757-5",

language = "English",

volume = "23",

pages = "647--657",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "6",

}

TY - JOUR

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

AU - Henning, Michael A.

AU - Yeo, Anders

PY - 2007/12

Y1 - 2007/12

N2 - 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.

AB - 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.

KW - Lower bounds

KW - Matching number

KW - Regular graph

UR - https://www.scopus.com/pages/publications/36949014140

U2 - 10.1007/s00373-007-0757-5

DO - 10.1007/s00373-007-0757-5

M3 - Article

AN - SCOPUS:36949014140

SN - 0911-0119

VL - 23

SP - 647

EP - 657

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 6

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this