Iteration index of a zero forcing set in a graph

MaRDI QIDQ2910019zbMATH OpenFDO

Authors Kiran B. Chilakamarri, Nathaniel Dean, Cong X. Kang, Eunjeong Yi

Publication date 7 September 2012

Published in Bulletin of the Institute of Combinatorics and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1105.1492

zbMATH Keywords

bouquet of circlesCartesian product of graphsiteration index of a zero forcing setzero forcing numberzero forcing set

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76) Applications of graph theory (05C90)

Abstract: Let each vertex of a graph G = (V(G), E(G)) be given one of two colors, say, "black" and "white". Let Z denote the (initial) set of black vertices of G. The color-change rule converts the color of a vertex from white to black if the white vertex is the only white neighbor of a black vertex. The set Z is said to be a zero forcing set of G if all vertices of G will be turned black after finitely many applications of the color-change rule. The zero forcing number of G is the minimum of |Z| over all zero forcing sets Z subseteq V (G). Zero forcing parameters have been studied and applied to the minimum rank problem for graphs in numerous articles. We define the iteration index of a zero forcing set of a graph G to be the number of (global) applications of the color-change rule required to turn all vertices of G black; this leads to a new graph invariant, the iteration index of G - it is the minimum of iteration indices of all minimum zero forcing sets of G. We present some basic properties of the iteration index and discuss some preliminary results on certain graphs.

Recommendations

• On zero forcing number of graphs and their complements
• Zero forcing propagation time on oriented graphs
• Probalistic zero forcing in graphs
• The zero forcing polynomial of a graph
• The failed zero forcing number of a graph

Cited in

(27)

• Computational approaches for zero forcing and related problems
• Some bounds on the zero forcing number of a graph
• Infection in hypergraphs
• Effects of vertex degrees on the zero-forcing number and propagation time of a graph
• Bounds on expected propagation time of probabilistic zero forcing
• Note on forcing problem of trees
• On the zero forcing number and propagation time of oriented graphs
• Upper bounds for positive semidefinite propagation time
• A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs
• Extremal k-forcing sets in oriented graphs
• On tight bounds for the \(k\)-forcing number of a graph
• Multi-color forcing in graphs
• Extremal values and bounds for the zero forcing number
• Using Markov chains to determine expected propagation time for probabilistic zero forcing
• Propagation time for zero forcing on a graph
• Upper bounds on the \(k\)-forcing number of a graph
• Zero forcing number of a graph in terms of the number of pendant vertices
• Propagation time for probabilistic zero forcing
• Connected zero forcing sets and connected propagation time of graphs
• On zero forcing number of graphs and their complements
• Zero forcing propagation time on oriented graphs
• The zero forcing number of graphs with the matching number and the cyclomatic number
• Maximum nullity, zero forcing number and propagation time of -path graphs
• Zero forcing number and propagation time discrepancy of some graphs
• Zero forcing number for Cartesian product of some graphs
• New structures and their applications to variants of zero forcing and propagation time
• Positive semidefinite propagation time

This page was built for publication: Iteration index of a zero forcing set in a graph

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