Differential in Cartesian Product Graphs

Abstract

Let \(\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 \(\partial(S) = |B(S)| – |S|\), and the differential of the graph \(\Gamma\) is defined as \(\partial(\Gamma) = \max\{\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 \(\Gamma_1 \times \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.