Notes on Fractional k-Covered Graphs

Authors: Sizhong Zhou, Yang Xu

Abstract:

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 .

Keywords: graph, binding number, fractional k-factor, fractional k-covered graph.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1085545

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.