Long dominating cycles and paths in graphs with large neighborhood unions
Broersma, H.J. and Veldman, H.J. (1991) Long dominating cycles and paths in graphs with large neighborhood unions. Journal of Graph Theory, 15 (1). pp. 2938. ISSN 03649024

PDF
408kB 
Abstract:  Let G be a graph of order n and define NC(G) = min. A cycle C of G is called a dominating cycle or Dcycle if V(G)  V(C) is an independent set. A Dpath is defined analogously. The following result is proved: if G is 2connected and contains a Dcycle, then G contains a Dcycle of length at least min unless G is the Petersen graph. By combining this result with a known sufficient condition for the existence of a Dcycle, a common generalization of Ore's Theorem and several recent neighborhood union results is obtained. An analogous result on long Dpaths is also established. 
Item Type:  Article 
Copyright:  © 1991 Wiley InterScience 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/70937 
Official URL:  http://dx.doi.org/10.1002/jgt.3190150106 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 140337