Graphs with Extremal Connected Forcing Numbers

Abstract

Zero forcing is an iterative graph coloring process where at each discrete time step, a colored vertex with a single uncolored neighbor forces that neighbor to become colored. The zero forcing number of a graph is the cardinality of the smallest set of initially colored vertices which forces the entire graph to eventually become colored. Connected forcing is a variant of zero forcing in which the initially colored set of vertices induces a connected subgraph; the analogous parameter of interest is the connected forcing number. In this paper, we characterize the graphs with connected forcing numbers 2 and $n-2$. Our results extend existing characterizations of graphs with zero forcing numbers 2 and $n-2$; we use combinatorial and graph theoretic techniques, in contrast to the linear algebraic approach used to obtain the latter. We also present several other structural results about the connected forcing sets of a graph.

arXiv comment24 pages, 9 figures

References in corpus (6)

• Full control by locally induced relaxation
• Propagation time for zero forcing on a graph
• Power domination and zero forcing
• Fractional Zero Forcing via Three-color Forcing Games
• Characterizations of the Connected Forcing Number of a Graph
• Metric Dimension and Zero Forcing Number of Two Families of Line Graphs