- Tytuł:
- Total Forcing Sets and Zero Forcing Sets in Trees
- Autorzy:
-
Davila, Randy
Henning, Michael A. - Powiązania:
- https://bibliotekanauki.pl/articles/31348333.pdf
- Data publikacji:
- 2020-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
forcing set
forcing number
total forcing set
total forcing number - Opis:
- A dynamic coloring of the vertices of a graph $G$ starts with an initial subset $S$ of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set $S$ is called a forcing set of $G$ if, by iteratively applying the forcing process, every vertex in $G$ becomes colored. If the initial set $S$ has the added property that it induces a subgraph of $G$ without isolated vertices, then $S$ is called a total forcing set in $G$. The minimum cardinality of a total forcing set in $G$ is its total forcing number, denoted $F_t(G)$. We prove that if $T$ is a tree of order $n ≥ 3$ with maximum degree $Δ$ and with $n_1$ leaves, then $n_1≤F_t(T)≤1/Δ((Δ-1)n+1)$. In both lower and upper bounds, we characterize the infinite family of trees achieving equality. Further we show that $F_t(T) ≥ F (T) + 1$, and we characterize the extremal trees for which equality holds.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2020, 40, 3; 733-754
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł