Tight lower bounds on the matching number in a graph with given maximum degree

Michael A. Henning*, Anders Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

105 Downloads (Pure)

Abstract

Let k≥3. We prove the following three bounds for the matching number, α(G), of a graph, G, of order n size m and maximum degree at most k. If k is odd, then (Formula presented.). If k is even, then (Formula presented.). If k is even, then (Formula presented.). In this article, we actually prove a slight strengthening of the above for which the bounds are tight for essentially all densities of graphs. The above three bounds are in fact powerful enough to give a complete description of the set Lk of pairs (γ,β) of real numbers with the following property. There exists a constant K such that 훼α(G)≥ γn+푚βm-k for every connected graph G with maximum degree at most k, where n and m denote the number of vertices and the number of edges, respectively, in G. We show that Lk is a convex set. Further, if k is odd, then Lk is the intersection of two closed half-spaces, and there is exactly one extreme point of Lk, while if k is even, then Lk is the intersection of three closed half-spaces, and there are precisely two extreme points of Lk.

Original languageEnglish
JournalJournal of Graph Theory
Volume89
Issue number2
Pages (from-to)115-149
ISSN0364-9024
DOIs
Publication statusPublished - 2018

Keywords

  • 05C70
  • convex set
  • matching number
  • maximum degree

Fingerprint

Dive into the research topics of 'Tight lower bounds on the matching number in a graph with given maximum degree'. Together they form a unique fingerprint.

Cite this