Notes on Fractional k-Covered Graphs

A graph G is fractional k-covered if for each edge e of G, there exists a fractional k-factor h, such that h(e) = 1. If k = 2, then a fractional k-covered graph is called a fractional 2-covered graph. The binding number bind(G) is defined as follows, bind(G) = min{|NG(X)| |X| : ├ÿ = X Ôèå V (G),NG(X) = V (G)}. In this paper, it is proved that G is fractional 2-covered if δ(G) ≥ 4 and bind(G) > 5 3 .

Authors:

• Sizhong Zhou
• Yang Xu

Keywords:

• graph
• binding number
• fractional k-factor
• fractional k-covered graph.

References:

[1] D.R. Woodall, The binding number of a graph and its Anderson number,
J.Combin. Theory ser. B 15(1973), 225-255.
[2] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, London,
The Macmillan Press, 1976.
[3] Edward R. Schinerman and D.H. Ullman, Fractional Graph Theory, John
Wiley and Son. Inc. New York, 1997.
[4] S. Zhou, Independence number, connectivity and (a, b, k)-critical graphs,
Discrete Mathematics 309(12)(2009), 4144-4148.
[5] S. Zhou, A new sufficient condition for graphs to be (g, f, n)-critical
graphs, Canadian Mathematical Bulletin, to appear.
[6] S. Zhou, A sufficient condition for a graph to be an (a, b, k)-critical
graph, International Journal of Computer Mathematics, to appear.
[7] S. Zhou and Y. Xu, Neighborhoods of independent sets for (a, b, k)-
Critical Graphs, Bulletin of the Australian Mathematical Society
77(2)(2008), 277-283.
[8] G. Liu and L. Zhang, Fractional (g, f)-factors of graphs, Acta Math.
Scientia (Ser. B) 21(4)(2001), 541-545.
[9] S. Zhou and Q. Shen, On fractional (f, n)-critical graphs, Information
Processing Letters 109(14)(2009), 811-815.
[10] S. Zhou, Some results on fractional k-factors, Indian Journal of Pure
and Applied Mathematics 40(2)(2009), 113-121.
[11] S. Zhou and H. Liu, Neighborhood conditions and fractional k-factors,
Bulletin of the Malaysian Mathematical Sciences Society 32(1)(2009),
37-45.
[12] S. Zhou and C. Shang, Some sufficient conditions with fractional
(g, f)-factors in graphs, Chinese Journal of Engineering Mathematics
24(2)(2007), 329-333.
[13] Z. Li, G. Yan and X. Zhang, On fractional f-covered graphs, OR
Trasactions (in Chinese) 6(4)(2002), 65-68.
[14] Z. Li, G. Yan and X. Zhang, Isolated toughness and fractional k-covered
graphs, Acta mathematicae Applicatae Sinica 27(4)(2004), 593-598.
[15] R. R. Anstee, An Algorithmic Proof Tutte-s f-Factor Theorem, J.
Algorithms 6(1985), 112-131.