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

I. Javaid, I. Irshad, M. Batool, Z. Raza

Published 2016-07-14Version 1

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}\geq2$ and $n_{2}\geq2$ 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\geq 2$ and an arbitrary graph $H$ containing $l\geq 1$ components $H_{1},H_{2}, \cdots,H_{l}$ with $|V(H_{i})|=m_{i}\geq 2$, $1\leq i\leq l$, $(n-1)l+\sum\limits_{i=1}^l m_{i}\leq Z(G\circ H)\leq n(\sum\limits_{i=1}^{l}m_{i})-l$.