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
![]() |
|
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 |