A neighborhood union condition for fractional $(k,n',m)$-critical deleted graphs

Document Type: Research Paper


1 Department of Editorial, Yunnan Normal University

2 Department of Applied Mathematics, Iran University of Science and Technology

3 School of Information and Technology, Yunnan Normal University


A graph $G$ is called a fractional‎ ‎$(k,n',m)$-critical deleted graph if any $n'$ vertices are removed‎ ‎from $G$ the resulting graph is a fractional $(k,m)$-deleted‎ ‎graph‎. ‎In this paper‎, ‎we prove that for integers $k\ge 2$‎, ‎$n',m\ge0$‎, ‎$n\ge8k+n'+4m-7$‎, ‎and $\delta(G)\ge k+n'+m$‎, ‎if‎ ‎$$|N_{G}(x)\cup N_{G}(y)|\ge\frac{n+n'}{2}$$‎ ‎for each pair of non-adjacent vertices $x$‎, ‎$y$ of $G$‎, ‎then $G$‎ ‎is a fractional $(k,n',m)$-critical deleted graph‎. ‎The bounds for‎ ‎neighborhood union condition‎, ‎the order $n$ and the minimum degree‎ ‎$\delta(G)$ of $G$ are all sharp‎.


Main Subjects

[1] J. A. Bondy and U. S. R. Mutry, Graph theory, Graduate Texts in Mathematics, 244, Springer, New York, 2008.
[2] W. Gao, Some results on fractional deleted graphs, Do ctoral disdertation of So o chow university, 2012.
[3] W. Gao and Y. Gao, Toughness condition for a graph to be a fractional (g, f, n)-critical deleted graph, The Scienti c World Jo., 2014, Article ID 369798, PP. 7, http://dx.doi.org/10.1155/2014/369798.
[4] W. Gao, L. Liang, T. W. Xu and J. X. Zhou, Tight toughness condition for fractional (g, f, n)-critical graphs, J. Korean Math. Soc., 51 (2014) 55-65.
[5] W. Gao and W. F. Wang, Toughness and fractional critical deleted graph, Util. Math., 98 (2015) 295-310.
[6] G. Liu and L. Zhang, Toughness and the existence of fractional k -factors of graphs, Discrete Math., 308 (2008) 1741-1748.
[7] J. Yu, G. Liu, M. Ma and B. Cao, A degree condition for graphs to have fractional factors, Adv. Math. (China), 35 (2006) 621-628.
[8] S. Z. Zhou, A minimum degree condition of fractional ( k ; m )-deleted graphs, C. R. Math. Acad. Sci., Paris, 347 (2009) 1223-1226.
[9] S. Z. Zhou, A neighb orho o d condition for graphs to b e fractional (k,m)-deleted graphs, Glasg. Math. J., 52 (2010) 33-40.
[10] S. Z. Zhou, A sufficient condition for a graph to b e a fractional ( f ; n )-critical graph, Glasg. Math. J. , 52 (2010) 409-415.
[11] S. Z. Zhou, A sufficient condition for graphs to b e fractional ( k ; m )-deleted graphs, Appl. Math. Lett., 24 (2011) 1533-1538.
[12] S. Z. Zhou and Q. Bian, An existence theorem on fractional deleted graphs, Period. Math. Hung., 71 (2015) 125-133.