NUMERICAL METHODS FOR PARTIAL DIFFERENTIAL EQUATIONS, vol.38, no.4, pp.936-946, 2022 (SCI-Expanded)
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 neighbor in the set D. The differential of a set D is defined as partial differential (D) = |B(D)| - |D| and the differential of a graph to equal the maximum value of partial differential (D) for any subset D of V. A set D of vertices of a graph G is said to be a dominating set if every vertex in V\D is adjacent to a vertex in D. G is a dominant differential graph if it contains a partial differential -set which is also a dominating set. Let G? be the complement of a graph G. The complementary prism GG? of G is the graph formed from the disjoint union of G and G? by adding the edges of a perfect matching between the corresponding vertices of G and G?. This paper is devoted to the computation of differential of complementary prisms GG?. Particular attention is given to the complementary prims of special types of graphs and dominant differential complementary prisms are recognized. Furthermore, a sharp lower bound on the differential of the complementary prism GG? of a graph G in terms of the order of G is presented and the graphs attaining this lower bound are characterized. Finally, the graphs G are characterized for which partial differential (GG?) is small.