The differential of the strong product graphs

Abstract

Let G = (V, E) be a graph of order n and let B(D) be the set of vertices in V \ D that have a neighbour in the set D. The differential of a set D is defined as ∂(D) = |B(D)| − |D| and the differential of a graph to equal the maximum value of ∂(D) for any subset D of V. In this paper we obtain several tight bounds for the differential of strong product graphs. In particular, we investigate the relationship between the differential of this type of product graphs and various parameters in the factors of the product.