Abstract
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 language | Undefined |
---|---|
Pages (from-to) | 29-40 |
Number of pages | 12 |
Journal | Journal of graph theory |
Volume | 0 |
Issue number | 15 |
DOIs | |
Publication status | Published - 1991 |
Keywords
- METIS-140337
- IR-70937