On Fractional (k,m)-Deleted Graphs with Constrains Conditions

Authors: Sizhong Zhou, Hongxia Liu

Abstract:

Let G be a graph of order n, and let k  2 and m  0 be two integers. Let h : E(G)  [0, 1] be a function. If e∋x h(e) = k holds for each x  V (G), then we call G[Fh] a fractional k-factor of G with indicator function h where Fh = {e  E(G) : h(e) > 0}. A graph G is called a fractional (k,m)-deleted graph if there exists a fractional k-factor G[Fh] of G with indicator function h such that h(e) = 0 for any e  E(H), where H is any subgraph of G with m edges. In this paper, it is proved that G is a fractional (k,m)-deleted graph if (G)  k + m + m k+1 , n  4k2 + 2k − 6 + (4k 2 +6k−2)m−2 k−1 and max{dG(x), dG(y)}  n 2 for any vertices x and y of G with dG(x, y) = 2. Furthermore, it is shown that the result in this paper is best possible in some sense.

Keywords: Graph, degree condition, fractional k-factor, fractional (k, m)-deleted graph.

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

References:

[1] S. Zhou, A neighborhood condition for graphs to be fractional (k,m)- deleted graphs, Glasgow Mathematical Journal 52(1)(2010), 33-40.
[2] S. Zhou, Independence number, connectivity and (a, b, k)-critical graphs, Discrete Mathematics 309(12)(2009), 4144-4148.
[3] S. Zhou and Q. Shen, On fractional (f, n)-critical graphs, Information Processing Letters 109(14)(2009), 811-815.
[4] H. Matsuda, Fan-type results for the existence of
[a, b]-factors, Discrete Mathematics 306(2006), 688-693.
[5] J. R. Correa and M. Matamala, Some remarks about factors of graphs, Journal of Graph Theory 57(2008), 265-274.
[6] H. Liu and G. Liu, Binding number and minimum degree for the existence of (g, f, n)-critical graphs, Journal of Applied Mathematics and Computing 29(1-2)(2009), 207-216.
[7] J. Yu and G. Liu, Fractional k-factors of graphs, Chinese Journal of Engineering Mathematics 22(2)(2005), 377-380.
[8] G. Liu and L. Zhang, Toughness and the existence of fractional k-factors of graphs, Discrete Mathematics 308(2008), 1741-1748.
[9] J. Cai and G. Liu, Stability number and fractional f-factors in graphs, Ars Combinatoria 80(2006), 141-146.
[10] S. Zhou, Some results on fractional k-factors, Indian Journal of Pure and Applied Mathematics 40(2)(2009), 113-121.
[11] S. Zhou, A minimum degree condition of fractional (k,m)-deleted graphs, Comptes rendus Mathematique 347 (21-22)(2009), 1223-1226.
[12] T. Niessen, A Fan-type result for regular factors, Ars combinatoria, 46(1997), 277-285.