Total forcing versus total domination in cubic graphs

摘要

A set S of vertices in a graph G is a total dominating set of G if every vertex has a neighbor in S. The total domination number, γt(G), is the minimum cardinality of a total dominating set of G. A total forcing set in a graph G is a forcing set (zero forcing set) in G which induces a subgraph without isolated vertices. The total forcing number of G, denoted Ft(G), is the minimum cardinality of a total forcing set in G. Our main contribution is to show that the total forcing number and the total domination number of a cubic graph are related. More precisely, we prove that if G is a connected cubic graph different from K3,3, then Ft(G)≤32γt(G).