Long dominating cycles in graphs
A cycle \(C\) in a graph \(G\) is a dominating cycle, or \(D\)-cycle, if \(V(G) - V(C)\) is an independent set in \(G\). Let \(\text{NC}2 = \text{ min} \{ |N(u) \cup N(v)|: \text{ dist} (u,v) = 2 \}\). This paper proves that if a graph on \(n\) vertices with minimum degree 2 contains a \(D\)-cycle, then it contains a \(D\)-cycle of length at least min\(\{ n, 2\text{NC}2-3 \}\). The authors suggest possible improvements to this and a related theorem.
scientific article; zbMATH DE number 1110123