On the Zero Forcing Number of Trees
Autor: | Mohammad Reza Oboudi |
---|---|
Rok vydání: | 2021 |
Předmět: |
General Mathematics
General Physics and Astronomy General Chemistry Time step law.invention Vertex (geometry) Combinatorics Set (abstract data type) Cardinality law Line graph Zero Forcing Equalizer General Earth and Planetary Sciences Graph (abstract data type) Tree (set theory) General Agricultural and Biological Sciences Mathematics |
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: |