More powerful closure operations on graphs (Q1174165): Difference between revisions

It is well known that for a (simple) graph \(G\) on \(n\) vertices and non- adjacent vertices \(u\neq v\) with degree sum \(d(u)+d(v)\geq n\) it holds: \(G\) is Hamiltonian iff \(G+uv\) is Hamiltonian. Thus, starting from \(G\) and joining pairs of non-adjacent vertices with degree sum \(\geq n\) successively, one obtains the \(n\)-closure \(C(G)\) of \(G\) and the corollary (\textit{Bondy, Chvátal}): \(G\) is Hamiltionian iff \(C(G)\) is Hamiltonian. This idea of a closure operation can be generalized to other properties of \(G\) (instead of Hamiltonicity) and, moreover, one can try to extend it to weaker degree sum conditions in order to make it more effective. Investigating this task the authors prove results of the following type: For non-adjacent vertices \(u\neq v\) in \(G\) let \(d(u)+d(v)\geq A_ i\); then \(G\) fulfils property \((E_ i)\) iff \(G+uv\) so does \((i=1,\ldots,13)\). Here, \(G\) fulfils \((E_ 1),\ldots,(E_{13})\) means: \(G\) is Hamiltonian, \(s\)-Hamiltonian, \(s\)-edge Hamiltonian, \(s\)-Hamiltonian connected, \(s\)- connected, \(s\)-edge connected, \(G\) contains a cycle of length \(s\), a path of length \(s-1\), a subgraph \(K_{2,s}\), an \(s\)-factor, \(G\) has edge independence number \(\geq s\), (vertex) independence number \(\leq s\), vertex path partition number \(\leq s\), respectively (\(s\) a positive integer). The bounds \(A_ i\) depend on \(n\), on the set \(R\), arising from the vertex set of \(G\) by deleting \(u,v\) and all neighbours of \(u\) and \(v\) in \(G\), and on further properties; e.g., for \(i=6\) (cycle of length \(s)\): \(A_ 6=2n-s-|\{x:x\in R, d(x)\geq| R|+n-s+\max(2,\theta)\}|\) with \(\theta=2n-s-d(u)-d(v)\).