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 .
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    24
    References
    10
    Citations
    NaN
    KQI
    []