Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

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