On the zero forcing number of corona and lexicographic product of graphs

Abstract

The zero forcing number of a graph $G$, denoted by $Z(G)$, is the minimum cardinality of a set $S$ of black vertices (where 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 turned black if it is the only white neighbor of a black vertex. In this paper, we study the zero forcing number of corona product, $G\odot H$ and lexicographic product, $G\circ H$ of two graphs $G$ and $H$. It is shown that if $G$ and $H$ are connected graphs of order $n_1\ge 2$ and $n_2\ge 2$ respectively, then $Z(G{\odot }^{k}H)=Z(G{\odot }^{k-1}H)+n_1(n_2+1{)}^{k-1}Z(H)$, where $G{\odot }^{k}H=(G{\odot }^{k-1}H)\odot H$. Also, it is shown that for a connected graph $G$ of order $n\ge 2$ and an arbitrary graph $H$ containing $l\ge 1$ components $H_1,H_2,\cdots ,H_l$ with $|V(H_i)|=m_i\ge 2$, $1\le i\le l$, $(n-1)l+\sum _{i=1}^l{m}_i\le Z(G\circ H)\le n(\sum _{i=1}^l{m}_i)-l$.

16 pages, 2 figures. arXiv admin note: text overlap with arXiv:1408.5943 by other authors