Independent cycles and chorded cycles in graphs
Independent cycles and chorded cycles in graphs
复制标题
图中的独立循环和弦循环
DOI：
10.4310/joc.2013.v4.n1.a6
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
P. Horn
中科院分区：
文献类型：
--
作者：
R. Gould;Kazuhide Hirohata;P. Horn
在这篇文章中，我们研究了图的独立顶点邻域的充分条件，这些条件意味着一个图包含k个独立圈或重叠圈。这与Corrádi和Hajna，Justesen，Wang和Faudree and Gould在含有k个独立圈的图上，以及Finkel在含有k个合唱圈的图上的几个结果有关。特别地，我们证明了如果G中的独立顶点至少有2k+1个邻域并，则G有k个合唱圈，只要|G|>；30k，解决了Faudree和Gould的一个猜想并改进了他们的一个结果，他们证明3k就足够了。此外，我们还证明了具有至少4k+1个独立顶点的邻域并的图至少有k个共鸣圈；Finkel以前证明了最小度3k也是这一点的充分条件。
In this paper, we investigate sufficient conditions on the neighborhood of independent vertices which imply that a graph contains k independent cycles or chorded cycles. This is related to several results of Corrádi and Hajnal, Justesen, Wang, and Faudree and Gould on graphs containing k independent cycles, and Finkel on graphs containing k chorded cycles. In particular, we establish that if independent vertices in G have neighborhood union at least 2k+ 1, then G has k chorded cycles, so long as |G| > 30k, and settling a conjecture of and improving a result of Faudree and Gould, who establish that 3k suffices. Additionally, we show that a graph with neighborhood union of independent vertices at least 4k + 1 has at least k chorded cycles; Finkel previously established that minimum degree 3k was also a sufficient condition for this.