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

PDF
 Accepted PostPrint Version
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, nm/d, d n/(D+d)\}. For the first two bounds, equality holds if and only if each component of G is rregular 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:  0166218X 
Date of First Compliant Deposit:  30 March 2016 
Date of Acceptance:  7 January 2015 
Last Modified:  19 Mar 2019 22:33 
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 