Long dominating cycles and paths in graphs with large neighborhood unions

Haitze J. Broersma, H.J. Veldman

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
122 Downloads (Pure)


Let G be a graph of order n and define NC(G) = min{|N(u)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.
Original languageUndefined
Pages (from-to)29-40
Number of pages12
JournalJournal of graph theory
Issue number15
Publication statusPublished - 1991


  • METIS-140337
  • IR-70937

Cite this