| The zero forcing number of a graph has many applications in control of quantum systems,monitoring of electrical networks,logic circuits and computer science.In this thesis,we mainly study the zero forcing number and its variants of graphs.Let G=(V,E)be a graph and S?V.The set S is a zero forcing set of G if iteratively adding vertices to S from V\S that are the unique neighbor in V\S of some vertex in S,results in the entire V of G.Moreover,if every vertex in S is within distance 2 of another vertex of S,then S is called a semitotal forcing set of G;if G[S]contains no isolated vertex,then S is called a total forcing set of G;if G[S]is connected,then S is called a connected forcing set of G.The zero forcing number F(G)(resp.,semitotal forcing number Ft2(G),total forcing number Ft(G),connected forcing number FC(G))is the minimum cardinality of a zero forcing set(resp.,semitotal forcing set,total forcing set,connected forcing set)in G.This thesis is divided into seven chapters,which mainly include the following contents:In Chapter 1,we first introduce the basic notations and definitions in graph theory.Secondly,introduce the research background and development of the zero forcing number of graphs.Then,we give three variants of zero forcing number and introduce their development.Finally,we list the main results of this thesis.In Chapter 2,we study the upper bound on the zero forcing number of a graph in terms of its order and degree and characterize the extremal graphs.Lu et al.in 2016 proposed a conjecture that if G is a connected graph with order n,maximum degree Δ≥2,minimum degree δ≥1,then F(G)=((Δ-2)n-(Δ-δ)+2)/Δ-1 if and only if either G=Cn,or G=Kn,or G=KΔ,Δ.We disprove this conjecture and characterize all connected graphs achieving F(G)=((Δ-2)n-(Δ-δ)+2)/Δ-1.Our result further generalizes the characterization of extremal regular graphs(i.e.,δ=Δ)obtained by Gentner et al.and Lu et al.in 2016.In Chapter 3,we investigate the zero forcing number and its variants of a graph G in terms of its order n and girth g.First,we propose three upper bounds on the zero forcing number according to different girth:F(G)≤n-g+2 when g=3,4 or n;F(G)≤n-g+1 when g=5,6 or n-1(n≥6)and F(G)≤n-g when 7≤g≤n-2.Further,the extremal graphs are characterized,respectively.Secondly,Davila et al.showed that if G is a 2-connected graph,then Fc(G)≤n-g+2.Based on this result,we completely characterize the 2-connected graphs attaining this upper bound,which are Cn,Kn,Ka,b(a,b≥2,a+b=n).Further,we can get similar results for semitotal forcing number and total forcing number of 2-connected graphs.In Chapter 4,we study extremal graphs with zero forcing number n-3.Recent results have classified all graphs on n vertices with zero forcing number 1,2,n-2,n-1.Alishahi et al.characterized all subcubic graphs with zero forcing number 3 in 2020.Inspired by them,we characterize all connected subcubic graphs G of order n with zero forcing number n-3,there are 18 graphs.Then,we characterize all connected triangle-free graphs G of order n with zero forcing number n-3,there are three families of graphs.In Chapter 5,we first prove that it is NP-complete to determine the semitotal forcing number of a graph.Secondly,we give a sharp upper bound on semitotal forcing number of a connected graph in terms of its order and maximum degree:if G≠Kn is a connected graph of order n≥4 with maximum degree Δ≥2,then Ft2(G)≤Δ-1/Δn,with equality if and only if either G=C4,or G=P4,or G=KΔ,Δ.In Chapter 6,we investigate the semitotal forcing number of a connected claw-free cubic graph G and give a sharp upper bound:if G≠K4 is a connected claw-free cubic graph of order n,then Ft2(G)≤3/8n+1.The graphs achieving equality in this bound are characterized,an infinite set of graphs.In Chapter 7,we make a summary and provide suggestions for future work and list several open problems. |
PDF Full Text Request