## 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 L_{k} 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 L_{k} is a convex set. Further, if k is odd, then L_{k} is the intersection of two closed half-spaces, and there is exactly one extreme point of L_{k}, while if k is even, then L_{k} is the intersection of three closed half-spaces, and there are precisely two extreme points of L_{k}.

Original language | English |
---|---|

Journal | Journal of Graph Theory |

Volume | 89 |

Issue number | 2 |

Pages (from-to) | 115-149 |

ISSN | 0364-9024 |

DOIs | |

Publication status | Published - 2018 |

## Keywords

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