Well-Forced Graphs

A graph in which all minimal zero forcing sets are in fact minimum zero forcing sets is called a well-forced graph. The main result of this paper is to characterize well-forced trees and based on this characterization present an algorithm for determining which trees are well-forced. As part of this characterization, certain subgraphs are identified as being forbidden in a well-forced graph. Additionally it is shown whether some common families of graphs are well-forced or not. Understanding well-forced graphs turns out to be closely related to the question of which vertices of a graph are in a minimal zero forcing set. A vertex of G that is in no minimal zero forcing set of G is called an irrelevant vertex. For any graph, a sufficient condition for a vertex to be irrelevant is established. In addition, it is proved that this condition is a characterization of irrelevant vertices in trees.