DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

R. Davila, M.A. Henning

Title:

Total forcing sets and zero forcing sets in trees

Source:

Discussiones Mathematicae Graph Theory

Received: 2017-09-28, Revised: 2018-03-13, Accepted: 2018-03-23, https://doi.org/10.7151/dmgt.2136

Abstract:

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 \ge 3$ with maximum degree $\Delta$ and with $n_1$ leaves, then $n_1 \le F_t(T) \le \frac{1}{\Delta}((\Delta - 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) \ge F(T)+1$, and we characterize the extremal trees for which equality holds.

Keywords:

forcing set, forcing number, total forcing set, total forcing number

PDF
Close