On zero forcing number of graphs and their complements
2015
The zero forcing number, Z(G), of a graph G is the minimum cardinality of a set S of black vertices (whereas vertices in V(G)\S are colored white) such that V(G) is turned black after finitely many applications of "the color-change rule": a white vertex is converted to a black vertex if it is the only white neighbor of a black vertex. Zero forcing number was introduced and used to bound the minimum rank of graphs by the "AIM Minimum Rank-Special Graphs Work Group". It is known that Z(G) ≥ δ(G), where δ(G) is the minimum degree of G. We show that Z(G) ≤ n - 3 if a connected graph G of order n has a connected complement graph . Further, we characterize a tree or a unicyclic graph G which satisfies either or .
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
24
References
10
Citations
NaN
KQI