On the Zero Forcing Number of Trees

Autor: Mohammad Reza Oboudi
Rok vydání: 2021
Předmět:
Zdroj: Iranian Journal of Science and Technology, Transactions A: Science. 45:1065-1070
ISSN: 2364-1819
1028-6276
Popis: Let G be a graph such that the color of its vertices is white or black. A dynamic vertex coloring for G is defined as follows. One starts with a certain set of black vertices. Then, at each time step, a black vertex with exactly one white neighbor forces its white neighbor to become black. The initial set of black vertices is called a zero forcing set if by iterating this process, all of the vertices of G become black. The zero forcing number of G (denoted by Z(G)) is the minimum cardinality of a zero forcing set in G. In this paper, we study the zero forcing number of trees. Let T be a tree with at least two vertices. We show that $$\Delta (T)-1\le Z(T)\le r(T)-1$$ , where $$\Delta (T)$$ and r(T) are the maximum degree and the number of pendant vertices of T, respectively. As a consequence, we obtain that $$Z(L(T))\ge Z(T)$$ , where L(T) is the line graph of T. We characterize all trees T such that $$Z(T)=\Delta (T)-1$$ . Finally, we study trees T with $$Z(T)= r(T)-1$$ .
Databáze: OpenAIRE
Externí odkaz: