Dominance Contraction Survey on Theory and Applications of Graphs

INTRODUCTION

The edge addition and removal in the dominance region have gained a lot of attention. There have been detailed investigations on changes in the conditions of dominance as a result of edge addition and deletion. In addition to addition and elimination, subdivision and contraction are the most critical operations on the graph's edges. It seems, however, that the area of dominance has been subject to subdivision and contraction only recently. Some research the effect of edge subdivision on the number of domination and absolute domination, two of the two most important parameters tested. The domination subdivision number sdμ(G) in a diagram is the minimum number of edges to subdivide in order to maximise the domination number (where the edge can be subdivided at the most at once). The first figure was established by Arumugam and Paulraj Joseph [1], which shows that sdα(T) <3 is at least three vertices for every tree T- and that this top bound is at least three vertices in each graph. However, Haynes and others[5] in 2001 gave the above conjecture a counter-example by showing that sdα(G) = 4 was used for cartesian product G = Kt – T > 4. The graph G with sd μg = 5 was developed later by Swaminathan and Sumathi[9]. [2, 3, 4] includes general limits for subdivision dominance numbers. The total subdivision number sdαt is a parallel definition (G). This number was defined in 2003 by Haynes et al. [<] with regard to vertex. They also showed that sd < 3 is sufficient for sd μt (G), and that sd < 3 is sufficient to indicate any T tree. The T-tree with sdβt (T) = 3 was constructively characterized[8]. [8]. This number can therefore be arbitrarily high in general graphs (see [7]). Motivated by recent research into subdivision, we take the edge contraction into account and add similar conceptions, namely the numbers for supremacy and overall dominance. We define the (total) domination number (ectβ(G)) ctα(G), as the minimum number of edges to be contract to lower the (total) domination number of graph G with (total) domination number at least (three) two. If the (total) dominance number is (two), then for simplicity, we define (ctβ (G))ctμ(G)=0. This will explain the importance of (total) dominance contraction number. One aim is to find a minimum (total) dominant set for useful installation in the corresponding graph G. In a facility location problem. If the cost of these facilities is to be cut, the total number of dominant installations must be decreased. In order to do so we must make some adjustments to the edges of G, i.e. add or contract certain edges. Formerly, the number of borders is increased and additional costs are therefore not necessary, whereas the latter is not (in fact, it decreases the number of edges, by Proposition2.1). The contraction of the edge therefore may be better than the addition of the edging. Then at least one needs to know how many edges to minimise the (total) dominance number need to be contracted. This question is answered by demonstrating that each of graphs G holds ctα <3 and ctαt (G)<3. An significant comparison with sdα(G) and sdμt is made with this result (G). Moreover, we give graph classifications and characterise them according to the two top limits of ctβ(G) and ctαt(G). We want to provide some terminology and notation prior to entering the next section. The contraction numbers of a chart are defined as equal to the

and edges set E=E is considered (G). To the vertex v {v} v (G), the open and closed v districts v must be N(v) and N[v] = N(v) {v}, respectively. The distance between two vertices x and y is showed with d(x, y). Denote the graph from G by contracting the edge e by G/e. Since edge contraction is a switchage process, i.e. (G/e)/f = (G/f)/e, on any of two edges e and f, we may use G/E′ to mark a resulting diagram of all edges in E′′ to build E(G) from G one by one. The reader is referred to as [10] for the terminology and graphic notation which is not given here. In G we say u dominates v if v [u], given two vertices u and v. G. G. A subset D § V(G) is referred to as the dominant set if its vertices dominate any vertex of G. G, denoted by β(G), is the minimum cardinality of all dominant sets. A dominant set of α(G) vertices is called shortly a β-set. A complete dominant set T is a dominant set with no isolated vertex in the induced subgram, which is that each vertex of G has a neighbour in T. The αt and αt-set complete dominance are similarly defined to β(G) and β-set. It is easy to see that βt for any unproductive graph is well established.

The chess freaks in Europe in 1850 thought of finding the smallest number of queens on a chess board with the intention that either a queen charges each of the blocks or a queen inhibits them. This dilemma gave birth to the theory of domination. Five queens were found to be sufficient to tower over the entire chess board (8*8). Here we are showing two of such arrangements of five queens such that all squares are dominated is shown in the following Fig Two arrangements of queens in 8*8 checker board in order to occupy every block by Queens. cardinality of an arrangement of domination. The Dominating set problem concerns finding a base dominating set.

For the graph G in Fig. 3, {1,3,5} is dominating set of cardinalities 3, {3,<,7,8} is a m dominating set of cardinalities four and {2,4,<,7,8} is a dominating set of cardinalities five. Hence the least cardinality is γ (G) = 3. Definition 2: Complete dominant known as an arrangement S of nodes in the graph G (V, E), given that each node V is attached to a component S and hence (G) is an overall dominance number. We envisage a PC arrangement for an application in which a group of servers can legally transmit from outside the core group for each PC. Furthermore, in any case, a separate "backup" file server where copy is stored is directly linked to each record server. A small community with this function is a μt collection made up of the framework. Definition 3: In graph of an edge dominating set G= (V, E) is subset S⊆E with the end goal that each arc not in S is adjoining to any one arc in S. An edge dominating set is otherwise known as line dominating set. Definition 4: A connected dominating set of a graph G is a dominating set D whose induced sub graph is also associated.

(i). node w in V(G) – S Γ (W) S = {v}. (ii). v is adjoining to no node of S.

The graphics of the domain is based on the passion of a few Chess players in 1850. In 1850. Data bank is the most commonly discussed from the various uses of dominance theory. The communications system consists of site-specific links. The problem is the limited destination arrangements where the senders are set to so that each other site is connected to the plot containing a sender with an immediate mail connection. In other words, the challenge is to find the least dominant figure in this system's graph. The problem for deciding the two disjoint transmission stations of the other set was considered by Kulli and Sigarkanti. This prompted them to define the reverse number of superiority. Definition <: An arrangement S of nodes in a Graph G is a dominating set if each node not in D is nearby any one node in S. In the event that V-S contains a dominating set say S' of G, at that point S ' is known as inverse dominating set concerning S. Example: 1 D1 = {2, 4}, D2 = {2, 5} and D3 = {1, 4} are the least dominating sets. Their comparing opposite inverse dominating sets are D1 * = {1, 3, 5}, D2 * = {1, 4} and D3 * = {2, 5} respectively. Thus, the domination number of G is γ(G) =2 & the inverse domination number of G is (G) = 2. Theorem 3.7: Let d be a positive divisor of a +ve number n. Then a regular graph G on n nodes, for γ (G) = (G) = d. Proof: Assume that d is a +ve number and divides n ≥ 1. i.e.; n = kd. Let V = Vi , where Vi = {vi1, vi2, ……, vid} for 1 ≤ i ≤ d. Let G be the graph with node set as V and every node of Vi is adjoining precisely to one node of V j , for j i. Then d(v) = k – 1 v ϵ V, so G is k – 1 regular. Also, each Vi is a γ – set of G. |E′ | and |E(G/E′ )| < |E(G)| − |E′ |. Proof. Note that contracting an edge decreases the number of vertices by one and the number of edges by at least one. The results follows by induction on |E′ |. Lemma 2. Let G be a connected graph. 1) If D is a γ-set of G and x, y are two vertices in D, then ctγ(G) < d(x, y). 2) If T is a γt-set of G and x, y, z are three vertices in D such that x, y are adjacent in G, then ctγt (G) < min{d(x, z), d(y, z)}. Proof. 1) Let P be a shortest path between x and y and consider G′ = G/E(P). We show γ(G′ ) < γ(G), which implies that ctγ(G) < |E(P)| = d(x, y). Suppose that D is a γ-set of G and v is the contracted vertex in G′ . Let D′ = (D \ V (P)) ∪ {v}. We will show that D′ is a dominating set of G′ . To this aim, consider u ∈ V (G′ ). If u ∈ N[v], then u is dominated by the contracted vertex v in G′. If u /∈ N[v], then u is also a vertex of G and so D contains a vertex w which dominates u in G. It is clear that w /∈ V (P)(otherwise u ∈ N[v]). It follows that w ∈ D′ , and w dominates u in G′ by the definition of contraction. Therefore D′ is a dominating set of G′ and γ(G′ ) < |D′ | = |D| − 1 = γ(G) − 1. 2) Suppose that T is a γt-set of G and x, y, z ∈ D satisfying xy ∈ E(G). Assume d(x, z) > d(y, z), without loss of generality. Let P be a shortest path between y and z. Then P does not contain x (otherwise d(x, z) < d(y, z)). We will show that γt(G/E(P)) < γt(G), which implies ctγt (G) < |E(P)| = d(y, z) = min{d(x, z), d(y, z)}. Denote the contracted vertex in G/E(P) by v and let T ′ = (T \V (P))∪ {v}. In order to prove T ′ is a total dominating set of G, we need only to consider each vertex u /∈ N[x]∪N[v], since x and v are two adjacent vertex in T ′ . Note that u is also a vertex of G. Then there exists a vertex w ∈ T such that uw ∈ E(G). It is clear that w /∈ V (P) (otherwise w ∈ N[v]). Hence w ∈ T ′ and uw ∈ E(G/E(P)) by the definition of contraction. Therefore T ′ is a total dominating set of G/E(P)), which implies that γt(G) < |T ′ | = |T | − 1 = γt(G) − 1. Now we investigate the relationship between the (total) dominating sets in the original graph and the (total) dominating sets in the contracted graph.

1) If D is a dominating set of G and E is a subset of E(G[D]), then G/E′ contains a dominating set D′ such that |D′ | = |D| − |E′ |. 2) If T is a total dominating set of G and E′ is a subset of E(G[T ]) such that G[T ]/E′ contains no isolated vertex, then G/E′ contains a total dominating set T ′ such that |T ′ | = |T | − |E′ |. Proof. 1) We will show that D′ = V (G[D]/E′ ) is a dominating set of G/E′ . Then |D′ | = |D| − |E′ | by Proposition 1. Let S be the set of all contracted vertices in G/E′ . Since E′ ⊆ E(G[D]), then S ⊆ D′ . Hence we need only to consider such vertex v that v /∈ N[s] for any s ∈ S. In that case, v is also a vertex of G. Thus D contains a vertex u ∈ D such that u = v or uv ∈ E(G). It is easy to observe that u is not incident with any edge of E′ ; otherwise u ∈ S, a contradiction to the assumption that v /∈ N[s] for any s ∈ S. Therefore u lies in D′ . If u = v then we are done. Otherwise u remains adjacent to v in G/E′ . Finally we conclude that D′ is a dominating set of G/E′ . 2) Since T is a dominating set of G, then by 1), T ′ is a dominating set of G/E′ and |T ′ | = |T | − |E′ |. Moreover, T ′ is a total dominating set, since G[T ′ ] = G[T ]/E′ contains no isolated vertex. Lemma 4 (Expansion Lemma) Let G be a connected graph. 1) If E′ is a subset of E(G) and D′ is a dominating set of G′ = G/E′ , then G has a dominating set D such that G′ [D′ ] is a spanning subgraph of G[D]/F where F ⊆ E(G[D]) and |F| = |E′ |. As a consequence, |D| = |D′ | + |E′ | and |E(G[D])| > |E(G′ [D′ ])| + |E′ |. 2) If E′ is a subset of E(G) and T ′ is a total dominating set of G′ = G/E′ , then G has a total dominating set T such that G′ [T ′ ] is a spanning subgraph of G[T ]/F where F ⊆ E(G[T ]) and |F| = |E′ |. As a consequence, |T | = |T ′ | + |E ′ | and |E(G[T ])| > |E(G′ [T ′ ])| + |E ′ |. Proof. 1) By induction on k = |E′ |. First consider k = 1. Suppose that E′ = {xy} and v is the contracted vertex in G′ = G/xy. We distinguish two cases. Case 1. v ∈ D′ . Let D = (D′ \ {v}) ∪ {x, y}. Then G[D]/xy = G′ [D′ ]. In order to show that D is a dominating set of G, we need only to consider such vertex u that u /∈ N[x] ∪ N[y]. Since u is also a vertex of G/xy, then D′ contains a vertex w which dominates u. It is easy to see w ∈ D since w ≠ v (otherwise u ∈ N[x] ∪ N[y] ). If u Case 2. v /∈ D′ . Then D′ contains a vertex z such that vz ∈ E(G′ ). Assume xz ∈ E(G), without loss of generality. Let D = D′ ∪ {x}. Then G′ [D′ ] is a spanning subgraph of G[D]/xz. To show that D is a dominating set of G, we need only to consider each vertex u /∈ {x, y} of G. Since u is also a vertex of G′ , then there exists a vertex w ∈ D′ ⊆ D such that u = w or uw ∈ E(G′ ). If u = w then we are done. Otherwise uw ∈ E(G′ ). Since v /∈ D′ , then w ≠ v, which implies uw ∈ E(G). Therefore D is a dominating set of G. Now consider k > 2 and let D′ be a dominating set of G′ = G/E′ . By the induction hypothesis, the result holds for E ′′ = E ′ \ {e} where e ∈ E ′ . Note that G/E′ = (G/e)/E′′. Then G′′ = G/e has a dominating set D′′ such that G ′ [D′ ] is a spanning subgraph of G ′′[D′′]/F′′ , |F ′′| = |E ′′|. (1) Applying the result of k = 1 to G′′ = G/e we have that G has a dominating set D such that G ′′[D ′′] is a spanning subgraph of G[D]/F′ , |F ′ | = 1. (2) Combining (1) and (2) yields that G has a dominating set D such that G′ [D′ ] is a spanning subgraph of (G[D]/F′ )/F′′ = G[D]/F where F = F ′ ∪ F ′′. It is easy to see that F ′′ ⊆ E(G′′[D′′]) \ E(G′ [D′ ]) and F ′ ⊆ E(G[D])\E(G′′[D′′]), which implies that |F| = |F ′′|+|F ′ | = |E′′|+1 = |E′ |. It follows from Proposition 1 that

|D| = |V (G[D])| = |V (G[D]/F)| + |F| = |V (G′ [D′ ])| + |E′ | = |D′ | + E′ |

and

|E(G[D])| > |E(G[D]/F)| + |F| > |E(G ′ [D ′ ])| + |E ′ |.

2) Let T ′ be a total dominating set of G′ = G/E′ . Then T ′ is a dominating set. By 1), G has a dominating set T such that G′ [T ′ ] is a spanning subgraph of G[T ]/F where F ⊆ E(G[T ]) and |F| = |E′ |. If G[T ] has an isolated vertex, then this vertex remains isolated in G[T ]/F. Hence G′ [T ′ ] contains an isolated vertex, since G′ [T ′ ] is a spanning subgraph of G[T ]/F. That contracts the hypothesis that T ′ is a total dominating set of G′ .

DOMINATION CONTRACTION NUMBER

In this section we consider domination contraction number of a graph. Let us begin with some simple examples. Proposition 1 For a path Pn and a cycle Cn on n vertices, γ(Pn) = γ(Cn) = ⌈ n 3 ⌉.

Theorem 1 For a connected graph G, ctγ(G) <3. Proof. Let D be a γ-set of G. If |D| = 1 then ctγ(G) = 0 by the definition. Assume |D| > 2 below. Choose two vertices x, y in D such that d(x, y) is as small as possible. We claim that d(x, y) <3, which implies ctγ(G) <3. Suppose to the contrary that d(x, y) = k > 4. Let P = xv1v2 . . . vk−1y be a shortest path between x and y. Then neither x nor y can dominate v2 since P is a shortest path. Thus there exists a vertex z in D \ {x, y} such that v2 ∈ N[z]. It follows that a contradiction to the choice of x, y. Next we determine when a graph has domination contraction number 0, 1, 2 or 3. Lemma 1 For a connected graph G, ctγ(G) = 0 if and only if G admits a star as its spanning tree. Proof. It is clear that γ(G) = 1 if and only if G has a vertex joined to all other vertices in G, i.e. G admits a star as its spanning tree. Lemma 2 For a connected graph G, ctγ(G) = 1 if and only if there exists a γ-set D which is not independent. Proof. If D is a γ-set which is not independent, then there exist two adjacent vertices x, y in D. By Lemma 2.2, ctγ(G) < d(x, y) = 1. Clearly ctγ(G) ≠ 0, since γ(G) = |D| > 2. Hence ctγ(G) = 1. Conversely, assume ctγ(G) = 1. Then there exists an edge xy such that γ(G/xy) = γ(G) − 1. Let D′ be a γ-set of G′ = G/xy. By the Expansion Lemma, G has a dominating set D such that |D| = |D′ |+1 and |E(G[D])| > |E(G′ [D′ ])| + 1 > 1. Then D is a γ-set of G since |D′ | = γ(G′ ) = γ(G) − 1, and D is not independent. By Lemma 2, a connected graph G has ctγ(G) <= 1 if and only if every γ-set of G is independent. As a consequence, γ(G) = i(G), where i(G) is the independent domination number of G, defined as the minimum cardinality of all maximal independent sets in G. However, we cannot conclude from γ(G) = i(G) that ctγ(G) ≠ 1. We go forward to characterize graphs with contraction domination number 2. For convenience, we call a dominating set D of G with |D| = γ(G)+1 a (γ + 1)-set. constraints to the numbers of dominance and absolute domination with those in subdivision numbers. These limitations allow graphs, as we have done to be clearly graded and characterised. We also have to concentrate on certain groups of graphs, like trees, and offer positive characteristics according to their numbers. The processes of graphs such as graphic products are also desirable for consideration. On the other hand, it is worth studying further the relationship between contraction numbers and subdivision numbers.

[1] S. Arumugam, J. Paulraj Joseph (1996). Domination in subdivision graphs. J. Indian Math. Soc. (N.S.), 62 (1-4), pp. 274-282. [2] A. Bhattacharya, G.R. Vijayakumar (2002). Effect of edge-subdivision on vertex-domination in a graph. Discuss. Math. Graph Theory, 22, pp. 335-347. [3] O. Favaron, T.W. Haynes, S.T. Hedetniemi (2004). Domination subdivision numbers in graphs. Util. Math., pp. 195-209. [4] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi (2000). Domination and independence subdivision numbers of graphs. Discuss. Math. Graph Theory, 20, pp. 271-280. [5] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs, J. Knisely, van der Merwe, C. Lucas (2001). Domination subdivision numbers. Discuss. Math. Graph Theory, 21, pp. 239-253. [6] T.W. Haynes, S.T. Hedetniemi, van der Merwe, C. Lucas (2003). Total domination subdivision numbers. J. Combin. Math. Combin. Comput., 44, pp. 115-128. [7] T.W. Haynes, M.A. Henning, L.S. Hopkins (2004). Total domination subdivision numbers of graphs. Discuss. Math. Graph Theory, 24, pp. 457-467. [8] T.W. Haynes, M.A. Henning, L. Hopkins (2004). Total domination subdivision numbers of trees. Discrete Math., 286, pp. 195-202. [9] V. Swaminathan and P. Sumathi (2003). Subdivision number of graphs and falsity of

[10] J.M. Xu (2003). Theory and Application of Graphs. Kluwer Academic Publishers, Dordrecht, Boston, London.

Assistant Professor of Mathematics, Sri Mahadeshwara Government First Grade College, Chamarajanagar, Kollegal, Karnataka