Independence number, connectivity and fractional (g,f)-factors in graphs
Author(s) -
Qiuju Bian,
Sizhong Zhou
Publication year - 2015
Publication title -
filomat
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.449
H-Index - 34
eISSN - 2406-0933
pISSN - 0354-5180
DOI - 10.2298/fil1504757b
Subject(s) - mathematics , combinatorics , independence number , graph , integer (computer science) , independence (probability theory) , discrete mathematics , statistics , computer science , programming language
Let $G$ be a graph, and let $g$ and $f$ be two integer-valued functions defined on $V(G)$ satisfying $a\leq g(x)\leq f(x)-r\leq b-r$ for any $x\in V(G)$, where $a,b$ and $r$ be three nonnegative integers with $1\leq a\leq b-r$. In this article, we verify that $G$ contains a fractional $(g,f)$-factor if its connectivity $\kappa(G)$ and independence number $\alpha(G)$ satisfy $\kappa(G)\geq\max\{\frac{(b+1)(b-r+1)}{2},\frac{(b-r+1)^{2}\alpha(G)}{4(a+r)}\}$. The result is best possible in some sense.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom