On the total forcing number of a graph

A total forcing set in a graph G is a forcing set (zero forcing set) in G which induces a subgraph without isolated vertices. Total forcing sets were introduced and first studied by Davila (2015). The total forcing number of G, denoted F-t (G) is the minimum cardinality of a total forcing set in G. We study basic properties of F-t (G), relate F-t (G) to various domination parameters, and establish NP-completeness of the associated decision problem for F-t (G). Our main contribution is to prove that if G is a connected graph of order n >= 3 with maximum degree Delta,then F-t (G) <= (Delta/Delta+1)n, with equality if and only if G is a complete graph K-Delta(+1), or a star K-1,K- Delta. (C) 2018 Elsevier B.V. All rights reserved.