A tight neighborhood union condition on fractional $(g,f,n’,m)$-critical deleted graphs

Wei Gao ¹   ; Weifan Wang ²

¹ School of Information Science and Technology Yunnan Normal University Kunming 650500, China
² Department of Mathematics Zhejiang Normal University Jinhua 321004, China

Colloquium Mathematicum, Tome 149 (2017) no. 2, pp. 291-298

Résumé

A graph $G$ is called a fractional $(g,f,n’,m)$-critical deleted graph if it remains a fractional $(g,f,m)$-deleted graph after deleting any $n’$ vertices. We prove that if $G$ is a graph of order $n$, $1\le a\le g(x)\le f(x)\le b$ for any $x\in V(G)$, $\delta (G)\ge {b^{2}/a}+n’+2m$, $n \gt {((a+b)(2(a+b)+2m-1)+bn’)/a}$, and $|N_{G}(x_{1})\cup N_{G}(x_{2})|\ge {b(n+n’)/(a+b)}$ for any nonadjacent vertices $x_{1}$ an $x_{2}$, then $G$ is a fractional $(g,f,n’,m)$-critical deleted graph. The result is tight on the neighborhood union condition in some sense.

Détail

DOI : 10.4064/cm6959-8-2016

Keywords: graph called fractional critical deleted graph remains fractional deleted graph after deleting vertices prove graph order delta m cup nonadjacent vertices fractional critical deleted graph result tight neighborhood union condition sense