Scholarlink

<p>Let <i>G</i> be a 2-connected graph of order <i>n</i>, and let <i>S</i> ⊆ <i>V</i>(<i>G</i>). A cycle <i>C</i> of <i>G</i> is <i>S</i>-maximum if no cycle <i>C</i>′ satisfies ∣<i>V</i>(<i>C</i>′) ⋂ <i>S</i> ∣ &gt; ∣<i>V</i>(<i>C</i>) ⋂ <i>S</i>∣; it is <i>S</i>-dominating if every vertex in <i>S</i> − <i>V</i>(<i>C</i>) has all neighbors on <i>C</i>. Denote by <i>σ</i><sub><i>k</i></sub>(<i>S</i>, <i>G</i>) the minimum degree sum in <i>G</i> of <i>k</i> independent vertices in <i>S</i> and by <i>δ</i>(<i>S</i>, <i>G</i>) the minimum degree in <i>G</i> among vertices in <i>S</i>. The circumference of a graph is the length of its longest cycle. Bondy (1980) proved that every longest cycle of <i>G</i> is <i>V</i>(<i>G</i>)-dominating if <i>σ</i><sub>3</sub>(<i>V</i>(<i>G</i>), <i>G</i>) ≥ <i>n</i> + 2. In this paper, we prove that if <i>σ</i><sub>3</sub>(<i>S</i>, <i>G</i>) ≥ <i>n</i> + 2, then <i>G</i> contains an <i>S</i>-maximum cycle that is <i>S</i>-dominating. This bound is sharp. Moreover, this result implies that the circumference of <i>G</i> is at least min{∣<i>S</i>∣, 2<i>δ</i>(<i>S</i>, <i>G</i>)} if <i>σ</i><sub>3</sub>(<i>S</i>, <i>G</i>) ≥ <i>n</i> + 2. As a corollary, we confirm a special case of Hao Li’s conjecture: “If <i>G</i> is a 2-connected graph of order <i>n</i> with at least <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\({{n + k} \over 2}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mfrac> <mrow> <mi>n</mi> <mo>+</mo> <mi>k</mi> </mrow> <mn>2</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation> vertices of degree at least <i>k</i>, then its circumference is at least min{<i>n</i>, 2<i>k</i>}.” We verify the conjecture when <i>n</i> ≤ 3<i>k</i> − 2 and at least 2<i>k</i> vertices have degree at least <i>k</i>. Note that the full conjecture has been shown to be false in general. Finally, we generalize the concept of relative length with respect to the cyclability of a vertex set.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On Cycles in 2-connected Graphs

  • 期刊论文

  • 发表日期：

    2025年12月8日

查看全文
  • Xia Li,
  • Ya-shu Li,
  • Wei-hua Yang

摘要

Let G be a 2-connected graph of order n, and let S ⊆ V(G). A cycle C of G is S-maximum if no cycle C′ satisfies ∣V(C′) ⋂ S ∣ > ∣V(C) ⋂ S∣; it is S-dominating if every vertex in S − V(C) has all neighbors on C. Denote by σk(S, G) the minimum degree sum in G of k independent vertices in S and by δ(S, G) the minimum degree in G among vertices in S. The circumference of a graph is the length of its longest cycle. Bondy (1980) proved that every longest cycle of G is V(G)-dominating if σ3(V(G), G) ≥ n + 2. In this paper, we prove that if σ3(S, G) ≥ n + 2, then G contains an S-maximum cycle that is S-dominating. This bound is sharp. Moreover, this result implies that the circumference of G is at least min{∣S∣, 2δ(S, G)} if σ3(S, G) ≥ n + 2. As a corollary, we confirm a special case of Hao Li’s conjecture: “If G is a 2-connected graph of order n with at least \({{n + k} \over 2}\) n + k 2 vertices of degree at least k, then its circumference is at least min{n, 2k}.” We verify the conjecture when n ≤ 3k − 2 and at least 2k vertices have degree at least k. Note that the full conjecture has been shown to be false in general. Finally, we generalize the concept of relative length with respect to the cyclability of a vertex set.