Sharp lower bounds on the fractional matching number

Behrend, Roger E., O, Suil and West, Douglas B. 2015. Sharp lower bounds on the fractional matching number. Discrete Applied Mathematics 186 , pp. 272-274. 10.1016/j.dam.2015.01.014

Preview

PDF - Accepted Post-Print Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (94kB) | Preview

Abstract

A fractional matching of a graph G is a function f from E(G) to the interval [0,1] such that \sum_{e\in\Gamma(v)}f(e) \le 1 for each v\in V(G), where \Gamma(v) is the set of edges incident to v. The fractional matching number of G, written \alpha'_*(G), is the maximum of \sum_{e\in E(G)}f(e) over all fractional matchings f. For G with n vertices, m edges, positive minimum degree d, and maximum degree D, we prove \alpha'_*(G) \ge \max\{m/D, n-m/d, d n/(D+d)\}. For the first two bounds, equality holds if and only if each component of G is r-regular or is bipartite with all vertices in one part having degree r, where r=D for the first bound and r=d for the second. Equality holds in the third bound if and only if G is regular or is (d,D)-biregular.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Uncontrolled Keywords:	fractional matching; Tutte's condition; biregular bipartite graph
Publisher:	Elsevier
ISSN:	0166-218X
Date of First Compliant Deposit:	30 March 2016
Date of Acceptance:	7 January 2015
Last Modified:	28 Nov 2020 13:29
URI:	http://orca.cf.ac.uk/id/eprint/70728

Citation Data

Cited 2 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item