Total Forcing Sets in Trees

arXiv1702.06496MaRDI QIDQ6283454FDOQ6283454

Authors: Randy Davila, Michael A. Henning 

Publication date: 21 February 2017

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 $nge3$ with maximum degree~$Delta$, then $F_t(T)lefrac1Delta((Delta-1)n+1)$, and we characterize the infinite family of trees achieving equality in this bound. We also prove that if $T$ is a non-trivial tree with $n_1$ leaves, then $F_t(T)ge{n}_1$, and we characterize the infinite family of trees achieving equality in this bound. As a consequence of this result, the total forcing number of a non-trivial tree is strictly greater than its forcing number. In particular, we prove that if $T$ is a non-trivial tree, then $F_t(T)geF(T)+1$, and we characterize extremal trees achieving this bound.

This page was built for publication: Total Forcing Sets in Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6283454)