A Study of the Theory of Graphs in Dominance Contraction Numbers
Exploring the Impact of Edge Contraction on Graph Theory and Applications
by Dr. Brijesh Kumar Sinha*,
- Published in Journal of Advances and Scholarly Researches in Allied Education, E-ISSN: 2230-7540
Volume 14, Issue No. 3, Feb 2018, Pages 449 - 456 (8)
Published by: Ignited Minds Journals
ABSTRACT
The effect of the edge contraction on the theory and applications of graphs is considered in this article. A minimum number of borders must be determined to reduce the (total) dominance number in a graph. We show that at most three are the two numbers for each diagram. In view of this result, the diagrams are classified and defined by (total) dominance contractions. The next article includes the concept of flat graphs, linked graphs, path dominance, graphic cycles and few features. We have also expanded our research into reverse applications for graphics and domains.
KEYWORD
theory of graphs, dominance contraction numbers, edge contraction, minimum number of borders, total dominance number, diagrams, classified, defined, flat graphs, linked graphs, path dominance, graphic cycles, reverse applications, graphics, domains
INTRODUCTION
The addition and removal of the edge in the dominant region have received considerable attention. Detailed investigations have been carried out into changes in dominance conditions due to edge addition and removal. In addition to addition and removal, the most critical operations on the edges of the graph are subdivision and contraction. However, it appears that the dominant area was only recently subdivided and contracted. Some researchers investigated the effect of the edge subdivision on number and absolute dominance, two of the two key parameters being tested. The sdμ(g) division in a diagram is the minimum number of arms to subdivide in order to maximize the number of domination (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 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 minimum value of the contraction numbers of all components of the chart. Thus only graph G = (V, E) connected to vertex set V=V(G) is taken into account 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.
DOMINATIONS IN GRAPHS
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 Definition 1: In a Graph G of dominating set S where each node of G is either in S or adjoining to any node in S. The domination number γ = γ (G) is the least cardinality of an arrangement of domination. The Dominating set problem concerns finding a base dominating set.
Planar graph
Non – Planar Graph
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. Definition 5: A dominating set S of a graph G is a minimal dominating set of G iff every node v in S fulfills in any of the accompanying two properties: (i). node w in V(G) – S Γ (W) S = {v}. (ii). v is adjoining to no node of S. In 1850 a few Chess players were passionate about the graphics of the domain. The most frequently discussed data bank is the dominant theory for different uses. There are site-specific links on the communication system. The problem is that the senders are set to a limited destination so that the plot contains a sender with an immediate mail connection is connected to one another. In other words, the challenge is to find in the graph of this system the least dominant figure. Kulli and Sigarkanti considered the problem of determining the two disjoint transmission stations in the other set. This led to the reversal of their superiority being defined. 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.
PRELIMINARIES
Proposition 1: If E′ ⊆ E(G), then |V (G/E′ )| = |V (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 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. Lemma 3 (Contraction Lemma) Let G be a connected 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 ′ |. 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 = w then we are done. Otherwise uw ∈ E(G′ ), which implies uw ∈ E(G). Thus D is a dominating set of G. 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 Applying the result of k = 1 to G′′ = G/e we have that G has a dominating set D such that 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 ⌉. Proposition 2 For a path Pn and a cycle Cn on n > 4 vertices, ctγ(Pn) = ctγ(Cn) = i, where n = 3k + i, 1 < i < 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.
CONCLUSION
There is an important comparison of the general 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.
REFERENCES
[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. graphs. Util. Math., <<, pp. 195-209. [4] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi (2002). 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 a conjecture. Electron. Notes Discrete Math., 15, Elsevier, Amsterdam. [10] J.M. Xu (2003). Theory and Application of Graphs. Kluwer Academic Publishers, Dordrecht, Boston, London.
Corresponding Author Dr. Brijesh Kumar Sinha*
Professor, Department of Mathematics, Galgotias University, Greater Noida, Uttar Pradesh, India
