2019/03/20 by Meysam Alishahi, Alishahi, Meysam, Elahe Rezaei-Sani +3
Computer Science · Mathematics · #Graph Labeling and Dimension Problems #Graph theory and applications #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1903.08614
A dynamic coloring of the vertices of a graph G starts with an initial subset F of colored vertices, with all remaining vertices being non-colored. At each time step, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set F is called a forcing set of G if, by iteratively applying the forcing process, every vertex in G becomes colored. The forcing number of a graph G, denoted by F(G), is the cardinality of a minimum forcing set of G. The maximum nullity of G, denoted by M(G), is defined to be the largest possible nullity over all real symmetric matrices A whose aij ≠ 0 for i ≠ j, whenever two vertices ui and uj of G are adjacent. In this paper, we characterize all graphs G of order n, maximum degree at most three, and F(G)=3. Also we classify these graphs with their maximum nullity.