Premium
Long dominating cycles and paths in graphs with large neighborhood unions
Author(s) -
Broersma H. J.,
Veldman H. J.
Publication year - 1991
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190150106
Subject(s) - combinatorics , mathematics , graph , generalization , path (computing) , order (exchange) , discrete mathematics , mathematical analysis , finance , computer science , economics , programming language
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.