A Neighborhood Condition for Fractional k-deleted Graphs

Authors: Sizhong Zhou, Hongxia Liu

Abstract:

Abstract–Let k ≥ 3 be an integer, and let G be a graph of order n with n ≥ 9k +3- 42(k - 1)2 + 2. Then a spanning subgraph F of G is called a k-factor if dF (x) = k for each x ∈ V (G). A fractional k-factor is a way of assigning weights to the edges of a graph G (with all weights between 0 and 1) such that for each vertex the sum of the weights of the edges incident with that vertex is k. A graph G is a fractional k-deleted graph if there exists a fractional k-factor after deleting any edge of G. In this paper, it is proved that G is a fractional k-deleted graph if G satisfies δ(G) ≥ k + 1 and |NG(x) ∪ NG(y)| ≥ 1 2 (n + k - 2) for each pair of nonadjacent vertices x, y of G.

Keywords: Graph, minimum degree, neighborhood union, fractional k-factor, fractional k-deleted graph.

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

References:

[1] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, London, The Macmillan Press, 1976.
[2] R. Schirerman Edward and H. Ullman Daniel, Fractional Graph Theory, John Wiley and Son. Inc. New York, 1997.
[3] J. R. Correa and M. Matamala, Some remarks about factors of graphs, Journal of Graph Theory 57(2008), 265-274.
[4] H. Matsuda, Fan-type results for the existence of (a, b)-factors, Discrete Mathematics 306(2006), 688-693.
[5] S. Zhou, Independence number, connectivity and (a, b, k)-critical graphs, Discrete Mathematics 309(12)(2009), 4144-4148.
[6] S. Zhou, A sufficient condition for a graph to be an (a, b, k)-critical graph, International Journal of Computer Mathematics 87(10)(2010), 2202-2211.
[7] S. Zhou, Remarks on (a, b, k)-critical graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 73(2010), 85-94.
[8] 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.
[9] G. Liu and L. Zhang, Toughness and the existence of fractional k-factors of graphs, Discrete Mathematics 308(2008), 1741-1748.
[10] J. Yu and G. Liu, Fractional k-factors of graphs, Chinese Journal of Engineering Mathematics 22(2)(2005), 377-380.
[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, Some results on fractional k-factors, Indian Journal of Pure and Applied Mathematics 40(2)(2009), 113-121.
[13] S. Zhou, A result on fractional k-deleted graphs, Mathematica Scandinavica 106(1)(2010), 99-106.
[14] K. Kotani, Binding numbers of fractional k-deleted graphs, Proceedings of the Japan Academy, Ser. A, Mathematical Sciences 86(2010), 85-88.
[15] T. Iida and T. Nishimura, Neighborhood conditions and k-factors, Tokyo Journal of Mathematics 20(2)(1997), 411-418.
[16] S. Zhou, A neighborhood condition for graphs to be fractional (k,m)- deleted graphs, Glasgow Mathematical Journal 52(1)(2010), 33-40.
[17] Z. Li, G. Yan and X. Zhang, On fractional (g, f)-deleted graphs, Mathematica Applicata (Wuhan) 16(1)(2003), 148-154.