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)
返 回