Graphs with Extremal Connected Forcing Numbers

arXiv1701.08500MaRDI QIDQ6282580FDOQ6282580

Authors: Boris Brimkov, Caleb C. Fast, Illya V. Hicks 

Publication date: 30 January 2017

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.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

This page was built for publication: Graphs with Extremal Connected Forcing Numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6282580)