Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph

Authors:	Michael A Henning Anders Yeo

Institution:	(1) School of Mathematical Sciences, University of KwaZulu-Natal, Pietermaritzburg, 3209, South Africa;(2) Department of Computer Science, Royal Holloway, University of London, Egham Surrey, TW20 OEX, UK

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 $\alpha'(G) \ge \min \left\{ \left( \frac{k^2 + 4}{k^2 + k + 2} \right) \times \frac{n}{2}, \frac{n-1}{2} \right\}$ , while if k is odd, then $\alpha'(G) \ge \frac{(k^3-k^2-2) \, n - 2k + 2}{2(k^3-3k)}$ . We show that both bounds are tight. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.

Keywords:	Lower bounds matching number regular graph
本文献已被 SpringerLink 等数据库收录！