Computing the differential in graphs

For every set D ⊆ V (G) of the graph G = (V (G),E(G)), for every set D ⊆ V (G), let B(D) be the set of vertices in V (G) \ D that have a neighbor in the vertex set D. The differential of the set D is defined as ∂(D) = |B(D)| − |D| and the differential of a graph G is defined as ∂(G) = max{∂(D) : D ⊆ V (G)}. A set D satisfying ∂(D) = ∂(G) is called a ∂-set or differential set. The research and application area of the differential of a graph is mainly computational mathematics. A set D of G is a dominating set if every vertex in V (G) \ D is adjacent to a vertex in D. A graph G is said to be dominant differential graph if it contains a ∂-set which is also a dominating set. In this thesis, firstly the differentials of path, cycle and wheel related graphs are computed and the graphs which are dominant differential are recognized. Then, the differentials of complementary prisms of specific types of graphs are computed and dominant differential complementary prisms are determined. Also, the differential of the complementary prism of a graph is investigated related to the parameters of that graph. Finally, an algorithm is proposed that computes the differential of a graph.