2017/02/20 by Davila, Randy, Henning, Michael A. · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1702.06035
Let G be a simple and finite graph without isolated vertices. In this paper we study forcing sets (zero forcing sets) which induce a subgraph of G without isolated vertices. Such a set is called a total forcing set, introduced and first studied by Davila \citeDavila. The minimum cardinality of a total forcing set in G is the total forcing number of G, denoted Ft(G). We study basic properties of Ft(G), relate Ft(G) to various domination parameters, and establish NP-completeness of the associated decision problem for Ft(G). We also prove that if G is a connected graph of order n ≥ 3 and maximum degree Δ, then Ft(G) ≤ ( \fracΔΔ+1 ) n, with equality if and only if G is a complete graph KΔ+ 1.