Long dominating cycles and paths in graphs with large neighborhood unions

Share/Save/Bookmark

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. 29-38. ISSN 0364-9024

[img]
Preview
PDF
398Kb
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.
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