<p>Let <i>G</i> be a connected graph. Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(t_1\geqslant 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>t</mi> <mn>1</mn> </msub> <mo>⩾</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(t_2\geqslant 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>t</mi> <mn>2</mn> </msub> <mo>⩾</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> be two integers with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(t_1\leqslant t_2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>t</mi> <mn>1</mn> </msub> <mo>⩽</mo> <msub> <mi>t</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>. Then <i>G</i> is two-disjoint-cycle-cover <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\([t_1,t_2]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">[</mo> <msub> <mi>t</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>t</mi> <mn>2</mn> </msub> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>-pancyclic or briefly 2-DCC <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\([t_1,t_2]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">[</mo> <msub> <mi>t</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>t</mi> <mn>2</mn> </msub> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>-pancyclic if for any integer <i>t</i> with <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(t_1\leqslant t\leqslant t_2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>t</mi> <mn>1</mn> </msub> <mo>⩽</mo> <mi>t</mi> <mo>⩽</mo> <msub> <mi>t</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>, <i>G</i> has two cycles <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(C_1\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(C_2\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> satisfying <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\vert V(C_1)\vert =t\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>V</mi> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> <mo>=</mo> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(V(C_2)=V(G)-V(C_1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>-</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. Let <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(q,w\in V(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>q</mi> <mo>,</mo> <mi>w</mi> <mo>∈</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(q\ne w\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>q</mi> <mo>≠</mo> <mi>w</mi> </mrow> </math></EquationSource> </InlineEquation> be two arbitrary vertices. Then <i>G</i> is 2-DCC vertex <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\([t_1,t_2]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">[</mo> <msub> <mi>t</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>t</mi> <mn>2</mn> </msub> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>-pancyclic if for any integer <i>t</i> with <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(t_1\leqslant t\leqslant t_2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>t</mi> <mn>1</mn> </msub> <mo>⩽</mo> <mi>t</mi> <mo>⩽</mo> <msub> <mi>t</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>, <i>G</i> has two cycles <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(C_1,C_2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>C</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(q\in V(C_1), w\in V(C_2)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>q</mi> <mo>∈</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>,</mo> <mi>w</mi> <mo>∈</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(\vert V(C_1)\vert =t\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>V</mi> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> <mo>=</mo> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(V(C_2)=V(G)-V(C_1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>-</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. We show that (<i>n</i>,&#xa0;1)-star graph <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\(S_{n,1}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mrow> <mi>n</mi> <mo>,</mo> <mn>1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> is 2-DCC edge <InlineEquation ID="IEq20"> <EquationSource Format="TEX">\([3,\lfloor \frac{n}{2}\rfloor ]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">[</mo> <mn>3</mn> <mo>,</mo> <mrow> <mo>⌊</mo> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> <mo>⌋</mo> </mrow> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>-pancyclic, 2-DCC vertex <InlineEquation ID="IEq21"> <EquationSource Format="TEX">\([3,\lfloor \frac{n}{2}\rfloor ]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">[</mo> <mn>3</mn> <mo>,</mo> <mrow> <mo>⌊</mo> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> <mo>⌋</mo> </mrow> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>-pancyclic and 2-DCC <InlineEquation ID="IEq22"> <EquationSource Format="TEX">\([3,\lfloor \frac{n}{2}\rfloor ]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">[</mo> <mn>3</mn> <mo>,</mo> <mrow> <mo>⌊</mo> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> <mo>⌋</mo> </mrow> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>-pancyclic when <InlineEquation ID="IEq23"> <EquationSource Format="TEX">\(n\geqslant 6\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>⩾</mo> <mn>6</mn> </mrow> </math></EquationSource> </InlineEquation>. We obtain that (<i>n</i>,&#xa0;<i>k</i>)-star graph <InlineEquation ID="IEq24"> <EquationSource Format="TEX">\(S_{n,k}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> is 2-DCC <InlineEquation ID="IEq25"> <EquationSource Format="TEX">\([3, \frac{n!}{2(n-k)!}]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">[</mo> <mn>3</mn> <mo>,</mo> <mfrac> <mrow> <mi>n</mi> <mo>!</mo> </mrow> <mrow> <mn>2</mn> <mo stretchy="false">(</mo> <mi>n</mi> <mo>-</mo> <mi>k</mi> <mo stretchy="false">)</mo> <mo>!</mo> </mrow> </mfrac> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>-pancyclic when <InlineEquation ID="IEq26"> <EquationSource Format="TEX">\(n\geqslant 8\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>⩾</mo> <mn>8</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq27"> <EquationSource Format="TEX">\(2 \leqslant k \leqslant n-6.\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mo>⩽</mo> <mi>k</mi> <mo>⩽</mo> <mi>n</mi> <mo>-</mo> <mn>6</mn> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation></p>

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

Two-Disjoint-Cycle-Cover Pancyclicity of (nk)-Star Graph

  • Jia Guo,
  • Mei Lu,
  • Dong-Qin Cheng

摘要

Let G be a connected graph. Let \(t_1\geqslant 3\) t 1 3 , \(t_2\geqslant 3\) t 2 3 be two integers with \(t_1\leqslant t_2\) t 1 t 2 . Then G is two-disjoint-cycle-cover \([t_1,t_2]\) [ t 1 , t 2 ] -pancyclic or briefly 2-DCC \([t_1,t_2]\) [ t 1 , t 2 ] -pancyclic if for any integer t with \(t_1\leqslant t\leqslant t_2\) t 1 t t 2 , G has two cycles \(C_1\) C 1 and \(C_2\) C 2 satisfying \(\vert V(C_1)\vert =t\) | V ( C 1 ) | = t and \(V(C_2)=V(G)-V(C_1)\) V ( C 2 ) = V ( G ) - V ( C 1 ) . Let \(q,w\in V(G)\) q , w V ( G ) with \(q\ne w\) q w be two arbitrary vertices. Then G is 2-DCC vertex \([t_1,t_2]\) [ t 1 , t 2 ] -pancyclic if for any integer t with \(t_1\leqslant t\leqslant t_2\) t 1 t t 2 , G has two cycles \(C_1,C_2\) C 1 , C 2 such that \(q\in V(C_1), w\in V(C_2)\) q V ( C 1 ) , w V ( C 2 ) , where \(\vert V(C_1)\vert =t\) | V ( C 1 ) | = t , \(V(C_2)=V(G)-V(C_1)\) V ( C 2 ) = V ( G ) - V ( C 1 ) . We show that (n, 1)-star graph \(S_{n,1}\) S n , 1 is 2-DCC edge \([3,\lfloor \frac{n}{2}\rfloor ]\) [ 3 , n 2 ] -pancyclic, 2-DCC vertex \([3,\lfloor \frac{n}{2}\rfloor ]\) [ 3 , n 2 ] -pancyclic and 2-DCC \([3,\lfloor \frac{n}{2}\rfloor ]\) [ 3 , n 2 ] -pancyclic when \(n\geqslant 6\) n 6 . We obtain that (nk)-star graph \(S_{n,k}\) S n , k is 2-DCC \([3, \frac{n!}{2(n-k)!}]\) [ 3 , n ! 2 ( n - k ) ! ] -pancyclic when \(n\geqslant 8\) n 8 and \(2 \leqslant k \leqslant n-6.\) 2 k n - 6 .