<p>For a graph <i>G</i> of order <i>n</i> and a positive integer <i>k</i>, a <i>k</i>-weak cycle partition of <i>G</i>, called <i>k</i>-WCP, is a sequence of vertex disjoint subgraphs <i>H</i><sub>1</sub>, <i>H</i><sub>2</sub>, ⋯, <i>H</i><sub><i>k</i></sub> of <i>G</i> with <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2025_8_Article_IEq1.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="144" /> </InlineMediaObject> <EquationSource Format="TEX">\(\bigcup\nolimits_{i=1}^{k} V(H_{i})=V(G)\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msubsup> <mo movablelimits="false">⋃</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow> <mi>k</mi> </mrow> </msubsup> <mi>V</mi> <mo stretchy="false">(</mo> <msub> <mi>H</mi> <mrow> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </math></EquationSource> </InlineEquation>, where <i>H</i><sub><i>i</i></sub> is isomorphic to <i>K</i><sub>1</sub>, <i>K</i><sub>2</sub> or a cycle. Let <i>σ</i><sub>2</sub>(<i>G</i>) = min{<i>d</i>(<i>x</i>) + <i>d</i>(<i>y</i>): <i>xy</i> ∉ <i>E</i>(<i>G</i>), <i>x, y</i> ∈ <i>V</i>(<i>G</i>)}. Hu and Li [Discrete Math. 307(2007)] proved that if <i>G</i> is a graph of order <i>n</i> ≥ <i>k</i> + 12 with a <i>k</i>-WCP and <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2025_8_Article_IEq2.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="111" /> </InlineMediaObject> <EquationSource Format="TEX">\(\sigma_{2}(G) \geq {{2n+k-4} \over 3}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msub> <mi>σ</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mrow> <mfrac> <mrow> <mn>2</mn> <mi>n</mi> <mo>+</mo> <mi>k</mi> <mo>−</mo> <mn>4</mn> </mrow> <mn>3</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation>, then <i>G</i> contains a <i>k</i>-WCP with at most one subgraph isomorphic to <i>K</i><sub>2</sub>. In this paper, we generalize their result on the analogy of Fan-type condition that <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2025_8_Article_IEq3.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="184" /> </InlineMediaObject> <EquationSource Format="TEX">\(\max\{{d(x),d(y)}\} \geq {{2n+k-4} \over 6}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mo form="prefix" movablelimits="true">max</mo> <mo fence="false" stretchy="false">{</mo> <mrow> <mi>d</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>,</mo> <mi>d</mi> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mrow> <mo fence="false" stretchy="false">}</mo> <mo>≥</mo> <mrow> <mfrac> <mrow> <mn>2</mn> <mi>n</mi> <mo>+</mo> <mi>k</mi> <mo>−</mo> <mn>4</mn> </mrow> <mn>6</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation> for each pair of nonadjacent vertices <i>x, y</i> ∈ <i>V</i>(<i>G</i>).</p>

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

Analogy of Fan-type Condition on Weak Cycle Partition of Graphs

  • Xiao-dong Chen,
  • Qing Ji,
  • Zhi-quan Hu

摘要

For a graph G of order n and a positive integer k, a k-weak cycle partition of G, called k-WCP, is a sequence of vertex disjoint subgraphs H1, H2, ⋯, Hk of G with \(\bigcup\nolimits_{i=1}^{k} V(H_{i})=V(G)\) i = 1 k V ( H i ) = V ( G ) , where Hi is isomorphic to K1, K2 or a cycle. Let σ2(G) = min{d(x) + d(y): xyE(G), x, yV(G)}. Hu and Li [Discrete Math. 307(2007)] proved that if G is a graph of order nk + 12 with a k-WCP and \(\sigma_{2}(G) \geq {{2n+k-4} \over 3}\) σ 2 ( G ) 2 n + k 4 3 , then G contains a k-WCP with at most one subgraph isomorphic to K2. In this paper, we generalize their result on the analogy of Fan-type condition that \(\max\{{d(x),d(y)}\} \geq {{2n+k-4} \over 6}\) max { d ( x ) , d ( y ) } 2 n + k 4 6 for each pair of nonadjacent vertices x, yV(G).