Long dominating cycles and paths in graphs with large neighborhood unions

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 , 2 NC ( 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.