Research On Related Problems Of Zero Forcing Sets

Given a vertex colouring of a graph G with black and white,the colour change rule is defined by:if u is a black vertex and exactly one neighbour v of u is white,then change the colour of v into black.After repeatedly applying this change rule,if all vertices become black,then the set of initial black vertices is called a zero forcing set of G.The zero forcing number is given by Z(G)=min{|U|:U(?)V(G),U is a zero forcing set of G},where V(G)is the set of all vertices of G.The first chapter introduces the research background and the main research results of this paper,some basic concepts are also given.In the second chapter,we improve the conclusion of Li and Sun[10]about the zero forcing number of trees.And on that basis,all trees satisflying Z(T)=p(T)-2 are characterized,where p(T)is the number of pendant vertices in T.Similarly,we characterize all trees that satisfy Z(T)=p(T)-3.In Chapter 3,in order to study the zero forcing set problem of infinite graphs,we give the definition of zero forcing density and the second density.For a d-dimensional infinite graph G,the zero forcing density is given by ?G=(?)Z(Gn)/|V(Gn)|,where {Gn} is any sequence of distinct finite subgraphs of G.When ?G=0,the second density is defined by ?'G=(?)Z(Gn)1/d-1/|V(Gn)|1/d.Considering the eleven Archimedean tilling graphs,we get upper bounds of the zero forcing density of the tilling graphs(34,6),(32,4,3,4),(4,82),(3,6,3,6),(3,122).The zero forcing density of the other six graphs is 0.And we obtain upper bounds of the second density of these six Archimedean tilling graphs.In Chapter 4,we prove the zero forcing density of n-dimensional lattice is 0,and give an upper bound of the second density of n-dimensional lattice.