A Neighborhood Condition for Fractional k-deleted Graphs
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.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1331639Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 774
 J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, London, The Macmillan Press, 1976.
 R. Schirerman Edward and H. Ullman Daniel, Fractional Graph Theory, John Wiley and Son. Inc. New York, 1997.
 J. R. Correa and M. Matamala, Some remarks about factors of graphs, Journal of Graph Theory 57(2008), 265-274.
 H. Matsuda, Fan-type results for the existence of (a, b)-factors, Discrete Mathematics 306(2006), 688-693.
 S. Zhou, Independence number, connectivity and (a, b, k)-critical graphs, Discrete Mathematics 309(12)(2009), 4144-4148.
 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.
 S. Zhou, Remarks on (a, b, k)-critical graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 73(2010), 85-94.
 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.
 G. Liu and L. Zhang, Toughness and the existence of fractional k-factors of graphs, Discrete Mathematics 308(2008), 1741-1748.
 J. Yu and G. Liu, Fractional k-factors of graphs, Chinese Journal of Engineering Mathematics 22(2)(2005), 377-380.
 S. Zhou and H. Liu, Neighborhood conditions and fractional k-factors, Bulletin of the Malaysian Mathematical Sciences Society 32(1)(2009), 37-45.
 S. Zhou, Some results on fractional k-factors, Indian Journal of Pure and Applied Mathematics 40(2)(2009), 113-121.
 S. Zhou, A result on fractional k-deleted graphs, Mathematica Scandinavica 106(1)(2010), 99-106.
 K. Kotani, Binding numbers of fractional k-deleted graphs, Proceedings of the Japan Academy, Ser. A, Mathematical Sciences 86(2010), 85-88.
 T. Iida and T. Nishimura, Neighborhood conditions and k-factors, Tokyo Journal of Mathematics 20(2)(1997), 411-418.
 S. Zhou, A neighborhood condition for graphs to be fractional (k,m)- deleted graphs, Glasgow Mathematical Journal 52(1)(2010), 33-40.
 Z. Li, G. Yan and X. Zhang, On fractional (g, f)-deleted graphs, Mathematica Applicata (Wuhan) 16(1)(2003), 148-154.