<p>The decycling number <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1972_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(\nabla (G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">∇</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of a graph <i>G</i> is the minimum number of vertices that must be removed to eliminate all cycles in <i>G</i>. The forest number <i>f</i>(<i>G</i>) is the maximum number of vertices that induce a forest in <i>G</i>. So <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1972_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="171" /> </InlineMediaObject> <EquationSource Format="TEX">\(\nabla (G) + f(G) = |V(G)|\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">∇</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">|</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> </mrow> </math></EquationSource> </InlineEquation>. For the Cartesian product <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1972_Article_IEq3.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">\(T \,\square \, T'\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mspace width="0.166667em" /> <mo>□</mo> <mspace width="0.166667em" /> <msup> <mi>T</mi> <mo>′</mo> </msup> </mrow> </math></EquationSource> </InlineEquation> of trees <i>T</i> and <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1972_Article_IEq4.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(T'\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>T</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> it is proved that <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1972_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="183" /> </InlineMediaObject> <EquationSource Format="TEX">\(\nabla (S_n \,\square \, S_{n'}) \le \nabla (T \,\square \, T')\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">∇</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>S</mi> <mi>n</mi> </msub> <mspace width="0.166667em" /> <mo>□</mo> <mspace width="0.166667em" /> <msub> <mi>S</mi> <msup> <mi>n</mi> <mo>′</mo> </msup> </msub> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mi mathvariant="normal">∇</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mspace width="0.166667em" /> <mo>□</mo> <mspace width="0.166667em" /> <msup> <mi>T</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, thus resolving the conjecture of Wang and Wu asserting that <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1972_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="176" /> </InlineMediaObject> <EquationSource Format="TEX">\(f(T \,\square \, T') \le f(S_n \,\square \, S_{n'})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>f</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mspace width="0.166667em" /> <mo>□</mo> <mspace width="0.166667em" /> <msup> <mi>T</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mi>f</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>S</mi> <mi>n</mi> </msub> <mspace width="0.166667em" /> <mo>□</mo> <mspace width="0.166667em" /> <msub> <mi>S</mi> <msup> <mi>n</mi> <mo>′</mo> </msup> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. It is shown that <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1972_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="278" /> </InlineMediaObject> <EquationSource Format="TEX">\(\nabla (T \,\square \, T') \ge \min \{ |V(T)|,|V(T')|\} - 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">∇</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mspace width="0.166667em" /> <mo>□</mo> <mspace width="0.166667em" /> <msup> <mi>T</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mrow> <mo movablelimits="true">min</mo> <mo stretchy="false">{</mo> <mo stretchy="false">|</mo> <mi>V</mi> </mrow> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mo stretchy="false">|</mo> <mo>,</mo> <mo stretchy="false">|</mo> <mi>V</mi> </mrow> <mrow> <mo stretchy="false">(</mo> <msup> <mi>T</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mrow> <mrow> <mo stretchy="false">|</mo> <mo stretchy="false">}</mo> </mrow> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and the equality cases characterized. For prisms over trees, it is proved that <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1972_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="141" /> </InlineMediaObject> <EquationSource Format="TEX">\(\nabla (T\,\square \, K_2) = \alpha '(T)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">∇</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mspace width="0.166667em" /> <mo>□</mo> <mspace width="0.166667em" /> <msub> <mi>K</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msup> <mi>α</mi> <mo>′</mo> </msup> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, and for arbitrary graphs <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1972_Article_IEq9.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">\(G_1\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1972_Article_IEq10.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">\(G_2\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation>, it is proved that <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1972_Article_IEq11.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="203" /> </InlineMediaObject> <EquationSource Format="TEX">\(\nabla (G_1 \,\square \, G_2) \ge \alpha '(G_1) \alpha '(G_2)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">∇</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>G</mi> <mn>1</mn> </msub> <mspace width="0.166667em" /> <mo>□</mo> <mspace width="0.166667em" /> <msub> <mi>G</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <msup> <mi>α</mi> <mo>′</mo> </msup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>G</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> <msup> <mi>α</mi> <mo>′</mo> </msup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>G</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1972_Article_IEq12.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(\alpha '\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>α</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> is the matching number.</p>

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

On Decycling and Forest Numbers of Cartesian Products of Trees

  • Ali Ghalavand,
  • Sandi Klavžar,
  • Ning Yang

摘要

The decycling number \(\nabla (G)\) ( G ) of a graph G is the minimum number of vertices that must be removed to eliminate all cycles in G. The forest number f(G) is the maximum number of vertices that induce a forest in G. So \(\nabla (G) + f(G) = |V(G)|\) ( G ) + f ( G ) = | V ( G ) | . For the Cartesian product \(T \,\square \, T'\) T T of trees T and \(T'\) T it is proved that \(\nabla (S_n \,\square \, S_{n'}) \le \nabla (T \,\square \, T')\) ( S n S n ) ( T T ) , thus resolving the conjecture of Wang and Wu asserting that \(f(T \,\square \, T') \le f(S_n \,\square \, S_{n'})\) f ( T T ) f ( S n S n ) . It is shown that \(\nabla (T \,\square \, T') \ge \min \{ |V(T)|,|V(T')|\} - 1\) ( T T ) min { | V ( T ) | , | V ( T ) | } - 1 and the equality cases characterized. For prisms over trees, it is proved that \(\nabla (T\,\square \, K_2) = \alpha '(T)\) ( T K 2 ) = α ( T ) , and for arbitrary graphs \(G_1\) G 1 and \(G_2\) G 2 , it is proved that \(\nabla (G_1 \,\square \, G_2) \ge \alpha '(G_1) \alpha '(G_2)\) ( G 1 G 2 ) α ( G 1 ) α ( G 2 ) , where \(\alpha '\) α is the matching number.