Let F(G) and <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1268_Article_IEq1.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> be the zero forcing number and the total forcing number of a graph G, respectively. In this paper, we study the relationship between the total forcing number of a graph and its vertex covering number (or independence number), and prove that <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1268_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="115" /> </InlineMediaObject> <EquationSource Format="TEX">$F_t(G) \le \Delta \alpha (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> <mo>≤</mo> <mi mathvariant="normal">Δ</mi> <mi>α</mi> <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="10878_2025_1268_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="184" /> </InlineMediaObject> <EquationSource Format="TEX">$F_t(G) \le (\Delta - 1)\beta (G) + 1$</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> <mo>≤</mo> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="normal">Δ</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mi>β</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> for any connected graph G with the maximum degree <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1268_Article_IEq4.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$\Delta $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Δ</mi> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1268_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="38" /> </InlineMediaObject> <EquationSource Format="TEX">$\alpha (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1268_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">$\beta (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>β</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> are the independence number and the vertex covering number of G. In particular, we prove that <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1268_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="157" /> </InlineMediaObject> <EquationSource Format="TEX">$F_t(T) \le F(T) + \beta (T)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mi>t</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mi>F</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mi>β</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for any tree T and characterize all trees T with <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1268_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="156" /> </InlineMediaObject> <EquationSource Format="TEX">$F_t(T) = F(T) + \beta (T)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mi>t</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>F</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mi>β</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. At the same time, all trees T with <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1268_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="181" /> </InlineMediaObject> <EquationSource Format="TEX">$F_t(T) = (\Delta - 1)\beta (T) + 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mi>t</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="normal">Δ</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mi>β</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> are completely characterized. In addition, we explore trees, unicycle graphs and Halin graphs satisfying <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1268_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="128" /> </InlineMediaObject> <EquationSource Format="TEX">$F(G) \le \alpha (G)+1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mi>α</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>.

Some results on the total (zero) forcing number of a graph

期刊论文
发表日期：

2025年3月10日

查看全文

Jianxi Li,
Dongxin Tu,
Wai Chee Shiu

摘要

Let F(G) and $F_t(G)$ $F_{t} (G)$ be the zero forcing number and the total forcing number of a graph G, respectively. In this paper, we study the relationship between the total forcing number of a graph and its vertex covering number (or independence number), and prove that $F_t(G) \le \Delta \alpha (G)$ $F_{t} (G) \leq Δ α (G)$ and $F_t(G) \le (\Delta - 1)\beta (G) + 1$ $F_{t} (G) \leq (Δ - 1) β (G) + 1$ for any connected graph G with the maximum degree $\Delta $ $Δ$ , where $\alpha (G)$ $α (G)$ and $\beta (G)$ $β (G)$ are the independence number and the vertex covering number of G. In particular, we prove that $F_t(T) \le F(T) + \beta (T)$ $F_{t} (T) \leq F (T) + β (T)$ for any tree T and characterize all trees T with $F_t(T) = F(T) + \beta (T)$ $F_{t} (T) = F (T) + β (T)$ . At the same time, all trees T with $F_t(T) = (\Delta - 1)\beta (T) + 1$ $F_{t} (T) = (Δ - 1) β (T) + 1$ are completely characterized. In addition, we explore trees, unicycle graphs and Halin graphs satisfying $F(G) \le \alpha (G)+1$ $F (G) \leq α (G) + 1$ .