Long dominating cycles and paths in graphs with large neighborhood unions
Hajo J. Broersma, H.J. Veldman · Journal of Graph Theory · 1991
Abstract Let G be a graph of order n and define NC(G) = min{|N(u) ∪ N(v)| |uv ∉ E(G)}. A cycle C of G is called a dominating cycle or D‐cycle if V(G) ‐ V(C) is an independent set. A D‐path is defined analogously. The following result is proved: if G is 2‐connected and contains a D‐cycle, then G contains a D‐cycle of length at least min{n, 2NC(G)} unless G is the Petersen graph. By combining this result with a known sufficient condition for the existence of a D‐cycle, a common generalization of Ore's Theorem and several recent “neighborhood union results” is obtained. An analogous result on long D‐paths is also established.