Differential in Cartesian Product Graphs

Abstract

Let $\mathrm{\Gamma }(V,E)$ be a graph of order $n$, $S\subset V$, and let $B(S)$ be the set of vertices in $V\setminus S$ that have a neighbor in $S$. The differential of a set $S$ is defined as $\mathrm{\partial }(S)=|B(S)|–|S|$, and the differential of the graph $\mathrm{\Gamma }$ is defined as $\mathrm{\partial }(\mathrm{\Gamma })=max\{\mathrm{\partial }(S):S\subset V\}$. In this paper, we obtain several tight bounds for the differential in Cartesian product graphs. In particular, we relate the differential in Cartesian product graphs with some known parameters of ${\mathrm{\Gamma }}_1\times {\mathrm{\Gamma }}_2$, namely, its domination number, its maximum and minimum degree, and its order. Furthermore, we compute explicitly the differential of some classes of product graphs.