<p>Let <i>S</i> be a subset of <i>V</i>(<i>G</i>). The vertices of <i>S</i> are colored black and the vertices of <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2925_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(V(G)-S\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>-</mo> <mi>S</mi> </mrow> </math></EquationSource> </InlineEquation> are colored white. The color-change-rule is defined as if a black vertex <i>u</i> has a unique white neighbor <i>v</i>, then we change the color of <i>v</i> from white to black. The initial <i>S</i> is called a zero forcing set if all vertices of <i>V</i> become black by iteratively applying the color-change-rule above. We call <i>S</i> a connected forcing set (resp. total forcing set) of <i>G</i> if <i>G</i>[<i>S</i>] is a connected subgraph (resp. a subgraph without isolated vertices). The minimum cardinality of zero forcing sets, connected forcing sets and total forcing sets are called zero forcing number, connected forcing number and total forcing number, denoted by <i>F</i>(<i>G</i>), <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2925_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="44" /> </InlineMediaObject> <EquationSource Format="TEX">\(F_c(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mi>c</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2925_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">\(F_t(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mi>t</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, respectively. Observe that <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2925_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="169" /> </InlineMediaObject> <EquationSource Format="TEX">\( F(G)\le F_t(G)\le F_c(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <msub> <mi>F</mi> <mi>t</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <msub> <mi>F</mi> <mi>c</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for a connected graph <i>G</i>, in particular, <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2925_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="194" /> </InlineMediaObject> <EquationSource Format="TEX">\( F(T)+1\le F_t(T)\le F_c(T)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mn>1</mn> <mo>≤</mo> <msub> <mi>F</mi> <mi>t</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <msub> <mi>F</mi> <mi>c</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for a tree <i>T</i>. In the paper, for a tree <i>T</i> we obtain a sharp upper bound of <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2925_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="104" /> </InlineMediaObject> <EquationSource Format="TEX">\(F_c(T)-F_t(T)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mi>c</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>-</mo> <msub> <mi>F</mi> <mi>t</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. In addition, we also characterize the structure of <i>T</i> with <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2925_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="105" /> </InlineMediaObject> <EquationSource Format="TEX">\(F_c(T)=F_t(T)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mi>c</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mi>F</mi> <mi>t</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2925_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="192" /> </InlineMediaObject> <EquationSource Format="TEX">\(F(T)+1=F_t(T)=F_c(T)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mn>1</mn> <mo>=</mo> <msub> <mi>F</mi> <mi>t</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mi>F</mi> <mi>c</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, respectively.</p>

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

The Extremal Results for Forcing Problem of Trees

  • Baoxin Li,
  • Yahan Cao,
  • Shengjin Ji

摘要

Let S be a subset of V(G). The vertices of S are colored black and the vertices of \(V(G)-S\) V ( G ) - S are colored white. The color-change-rule is defined as if a black vertex u has a unique white neighbor v, then we change the color of v from white to black. The initial S is called a zero forcing set if all vertices of V become black by iteratively applying the color-change-rule above. We call S a connected forcing set (resp. total forcing set) of G if G[S] is a connected subgraph (resp. a subgraph without isolated vertices). The minimum cardinality of zero forcing sets, connected forcing sets and total forcing sets are called zero forcing number, connected forcing number and total forcing number, denoted by F(G), \(F_c(G)\) F c ( G ) and \(F_t(G)\) F t ( G ) , respectively. Observe that \( F(G)\le F_t(G)\le F_c(G)\) F ( G ) F t ( G ) F c ( G ) for a connected graph G, in particular, \( F(T)+1\le F_t(T)\le F_c(T)\) F ( T ) + 1 F t ( T ) F c ( T ) for a tree T. In the paper, for a tree T we obtain a sharp upper bound of \(F_c(T)-F_t(T)\) F c ( T ) - F t ( T ) . In addition, we also characterize the structure of T with \(F_c(T)=F_t(T)\) F c ( T ) = F t ( T ) and \(F(T)+1=F_t(T)=F_c(T)\) F ( T ) + 1 = F t ( T ) = F c ( T ) , respectively.