Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Sharp lower bounds on the fractional matching number

Behrend, Roger E. ORCID:, 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

[thumbnail of SharpLowerBoundsOnTheFractionalMatchingNumber-January2015.pdf]
PDF - Accepted Post-Print Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (94kB) | Preview


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: 07 Nov 2023 00:57

Citation Data

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

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics