Sharp lower bounds on the fractional matching number

被引：7

作者：

Behrend, Roger E. ^{[1
]}

Suil, O. ^{[2
]}

West, Douglas B. ^{[3
,4
]}

机构：

[1] Cardiff Univ, Sch Math, Cardiff CF24 4AG, S Glam, Wales

[2] Georgia State Univ, Dept Math, Atlanta, GA 30303 USA

[3] Zhejiang Normal Univ, Dept Math, Jinhua, Peoples R China

[4] Univ Illinois, Dept Math, Urbana, IL 61801 USA

来源：

DISCRETE APPLIED MATHEMATICS | 2015年 / 186卷

关键词：

Fractional matching; Tutte's condition; Biregular bipartite graph;

D O I：

10.1016/j.dam.2015.01.014

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A fractional matching of a graph G is a function f from E(G) to the interval [0, 1] such that Sigma(e is an element of Gamma(v))f(e) <= 1 for each v is an element of 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 Sigma(e is an element of 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) >= max{m/D, n - m/d, d/D+dn}. 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. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：272 / 274

页数：3