The Domination Subdivision Number and Bondage Number Using Cartesian product Graph

Abstract

Domination is a famous and interesting area of research in graph theory. The applications of domination are in a variety of fields like design and analysis of communication networks, bio-informatics, computational complexity and designing algorithm. In a Graph G, a set S С V is said to be a dominating set of G, if every vertex outside of the set S has a neighbor in S. The domination subdivision number of a graph G is the minimum number of edges that must subdivided in order to increase the domination number of a graph and it is denoted by sdγ(G). The Bondage number of a graph G is the minimum number of edges whose removal increases the domination number of a graph G.The Cartesian product of G and H written as G×H, is the graph with vertex set V(G)×V(H) specified by putting (u,v) adjacent to (u',v') if and only if (i) u=u' and vv' belongs to E(H), or (ii) v=v' and uu' belongs to E(G). For any graph G of order n≥3,sdγ(T)≤δ(G)+1 proved by T.W. Haynes, S.M.Hedetniemi, T. Hedetniemi, D.P.Jacobs,J.Knisely,L.C.Van der Merve . Now I am going to prove sdγ(G)<δ(G)+1 for the Cartesian product of the graph G of Pn×Pn of order n≥3 and also Bondage number of G is atmost 2.