Zero forcing in iterated line digraphs

Daniela Ferrero, Thomas Kalinowski, Sudeep Stephen

Published 2017-08-10Version 1

We prove that the iterated application of the line digraph operator permits to obtain arbitrarily large families of graphs with optimal properties in regards to minimum rank, zero forcing and power domination. We construct minimum zero forcing and power dominating sets in iterated line digraphs and derive bounds for their zero forcing and power domination number. Through the relationship between zero forcing, minimum rank and power domination, we show that for any $d$-regular digraph $G$, $d\geq 2$, and any positive integer $n$, the $n$-iterated line digraph of $G$ has zero forcing and maximum nullity $(d-1)d^{n-1}|G|$ and power domination number $(d-1)d^{n-2}|G|$, if $n\geq 2$. As an application, we obtain the value of those parameters for some important families of digraphs such as de Bruijn, Kautz, generalized de Bruijn, generalized Kautz and wrapped butterflies.