Stable properties of graphs (Q1175986)

Local generalizations of some results obtained by \textit{J. A. Bondy} and \textit{V. Chvatal} in [Discrete Math. 15, 111-135 (1976; Zbl 0331.05138)] are presented. Let \(d_ G(u,v)\) be the distance between vertices \(u\) and \(v\) in a graph \(G\). Then for any \(u\in V(G)\) we denote by \(N^ k_ G(u)\) and \(M^ k_ G(u)\) the sets of all \(v\in V(G)\) with \(d_ G(u,v)=k\) and \(d_ G(u,v)\leq k\), respectively. The property \(P\) is \((k,r)\)-stable, \(k\geq 2\), if whenever \(G+uv\) has property \(P\) and \[ d_ G(u)+d_ G(v)\geq| M^ k_ G(u)|+| N_ G^{k+1}(u)\cap N^ 1_ G(v)|+r\tag{1} \] then \(G\) itself has property \(P\). Theorem 1. The property of containing of a hamiltonian cycle is (2,0)- stable. \(A (k,r)\)-closure of \(G\) is a graph obtained from \(G\) by recursively joining pairs of nonadjacent vertices satisfying the condition (1). A graph is constructed in which the \((k,r)\)-closure is not unique. Theorem 2. For every \(n\geq 6\) there is a graph \(G\) such that \(| V(G)|=n\), \(| E(G)|=2n-3\) and \(K_ n\) is a (2,0)-closure of \(G\). Theorem 3. Let \(G\) be a 2-connected graph of order \(n\), \(n\geq 3\), and let \(u\) and \(v\) be distinct vertices of \(G\). If \(d_ G(u,v)=2\) implies \(\max\{d_ G(u),d_ G(v)\}\geq{n\over 2}\), then \(K_ n\) is a (2,0)- closure of \(G\). Furthermore, it is shown that the property of containing a cycle \(C_ s (C_{2t})\) is \((2,n-s)\)-stable \(((4,n-s-1)\)-stable), the property of containing a path \(P_ s\) is \((4,-1)\)-stable and \((2,0)\)-stable, the property of being \(s\)-edge-hamiltonian is \((2,s)\)-stable, the property of being \(s\)-hamiltonian is \((2,s)\)-stable, the property of being \(s\)- hamiltonian-connected is \((2,s+1)\)-stable, the property of containing \(K_{2,s}\), the property of being \(s\)-connected and the property of being \(s\)-edge-connected are \((2,s-2)\)-stable.