# On Zero Forcing Number of Graphs and Their Complements

Research paper by **Linda Eroh, Cong X. Kang, Eunjeong Yi**

Indexed on: **27 Dec '14**Published on: **27 Dec '14**Published in: **Mathematics - Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

The \emph{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) \setminus
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's known that $Z(G)\geq \delta(G)$, where
$\delta(G)$ is the minimum degree of $G$. We show that $Z(G)\leq n-3$ if a
connected graph $G$ of order $n$ has a connected complement graph
$\overline{G}$. Further, we characterize a tree or a unicyclic graph $G$ which
satisfies either $Z(G)+Z(\overline{G})=\delta(G)+\delta(\overline{G})$ or
$Z(G)+Z(\overline{G})=2(n-3)$.