首页   按字顺浏览 期刊浏览 卷期浏览 Long dominating cycles and paths in graphs with large neighborhood unions
Long dominating cycles and paths in graphs with large neighborhood unions

 

作者: H. J. Broersma,   H. J. Veldman,  

 

期刊: Journal of Graph Theory  (WILEY Available online 1991)
卷期: Volume 15, issue 1  

页码: 29-38

 

ISSN:0364-9024

 

年代: 1991

 

DOI:10.1002/jgt.3190150106

 

出版商: Wiley Subscription Services, Inc., A Wiley Company

 

数据来源: WILEY

 

摘要:

AbstractLetGbe a graph of ordernand defineNC(G)= min{|N(u) ∪N(v)| |uv∉E(G)}. A cycleCofGis called adominating cycleorD‐cycleifV(G) ‐V(C) is an independent set. AD‐pathis defined analogously. The following result is proved: ifGis 2‐connected and contains aD‐cycle, thenGcontains aD‐cycle of length at least min{n, 2NC(G)} unlessGis the Petersen graph. By combining this result with a known sufficient condition for the existence of aD‐cycle, a common generalization of Ore's Theorem and several recent “neighborhood union results” is obtained. An analogous result on longD‐pa

 

点击下载:  PDF (412KB)



返 回