Santhosh M

INTRODUCTION One of the fastest growing areas in graph theory is the study of domination. It takes back to 1850’s with the study of the problem of determining the minimum number of queen which are necessary to cover an n*n chessboard. More than 50 types of domination parameters have been studied by different authors. Ore, Berg introduced the concept of domination sets. Extensive research activity is going on in Domination set of graphs. Acharya B.D, SampathKumar.E, V.R Kulli, Waliker H.B are some of the Indian Mathematicians who have made substantial contribution to the study of domination in graphs. Domination is applied in many fields. Some of them are 1. Communication network 2. Facility location problem 3. Land surveying 4. Routings etc., In this project discuss the concept of dominations directed graphs.A directed graph(digraph) is a set of vertices and a collection of directed edges that each connects an ordered pair of vertices(nodes). A directed graph is a pair G = (V,A), Where V is a set of nodes and Ais a set of arcs, A set of vertices is a dominating set of G if each vertex is dominated by atleast a vertex in S. A dominating set S of a digraph D is maximal dominating set if V-S is not a dominating set of D. A total dominating set S of a digraph D is maximal, if V-S is not a total dominating set. A minimal dominating set is a dominating set of minimal cardinality of D and its cardinality is the domination number of D. V.R Kulli introduced the concept of inverse domination and inverse total domination, Let S be a minimum dominating set of G. if V-S contains a dominating set S’ of G, then S’ is called an inverse dominating set with respect to S. The inverse domination number of G is the minimum cardinality of G. Similarlly, S be a minimum total dominating set of G. if V-S contains a total dominating set S’of G, then S’ is called inverse total domination with respect to S. The minimum cardinality S’ is the inverse total domination number of G. In this paper, we initiate a study of maximal and maximal total dominations in digraphs, How to incrementally compute a minimal dominating set on digraphs. We introduce the analog of inverse domination and inverse total domination in digraphs and we obtain several results on these parameters. We also determine the domination number of a random digraph. - Domination number of D – Total domination number of D – Maximal domination number of D – Maximal total domination number of D – Inverse domination number of D CHAPTER – I Basic Definitions 1.1 Graph A graph G=(V, E) consists of a set of objects V={V1,V2….Vn} called vertices and another set E={e1,e2. . .} whose elements are called edges such that each edge is identified with an unordered pair (Vi, Vj) of vertices. 1.2 Sub Graph A graph H is a subgraph of a graph if all the vertices and all the edge of H, are in G and edge of H has the same and vertices in G. 1.3 Regular Graph A graph in which every vertex have same degree is called regular graph 1.4 Complete Graph A simple graph in which each pair of distinct vertices is joined by an edge is called a completed graph. A complete graph with n vertices is denoted by kn. 1.5 Simple Graph A graph is said to be simple if it has no loops and multiple lines 1.6 Multigraph If more than one line joining two vertices and are allowed the resulting object is called a Multigraph 1.7 Null graph A graph whose edge set is empty is called a null graph or a totally disconnected graph. 1.8 Degree of a graph The degree of a point Vi in a graph G is the number of lines incident with Vi The degree of Vi is denoted by deg (Vi) or d (Vi) 1.9 Isolated Point A point V of degree 0 is called Isolated Point. 1.10 End Point A point V of degree 1 is called on End Point. 1.11 Connected Graph A Graph G is said to be connected, if any two of its points can be connected by a path. 1.12 Disconnected Graph A Graph which is not connected is said to be disconnected Example 1.13 A Cyclic Graph A graph that contains no cycles is called an a cyclic graph. Example 1.14 Unicyclic Graph It is a connected graph with exactly one cycle 1.15 walk A walk is an alternating sequence of vertices and edges, beginning and ending with vertex. 1.16 Closed walk A walk which begins and ends with the same vertex is called a closed walk. Example 1.17 Open walk A walk in which the initial and terminal vertices are different is called an open walk. Example 1.18 Path An open walk in which no vertex appears more than once is called a path. Example 1.19 Cycle A cycle is a path such that start vertex and end vertex are the same. Example 1.20 Simple bipartite graph A complete bipartite graph is a simple bipartite graph with partition (X, Y) in which each vertex of X is jointed to each vertex of Y. It is denoted by Km,n. 1.21 Dominating Set A dominating set for a graph G=(V,E) is a subset D of V such that every vertex not member of D by some edge. A set D of vertices in a graph G is called a dominating set of G if every vertex in V-D is adjacent to some vertex in D. Example The set D={A,B,E,H} is one of the dominating set 1.22 Minimum Dominating Set A Dominating set D is said to be minimum dominating set if D consist of minimum number of vertices among all dominating set . Example 1.23 Dominating Number The dominating number r(G) is the number of vertices in a smallest dominating set for G. 1.24 Minimal Dominating set A dominating set D is called Minimal dominating set if no proper subset of D is a dominating set. Example 10 The set {B,C,E},{D,C},and {B,E,F,G} are minimal dominating set A minimal dominating set is a minimal dominating set, but the converse is not always true. 1.25 Total Dominating Set A dominating set D of a graph G is a total dominating set if the induced sub-graph has no isolated vertices. That is Every vertex of G is adjacent to at least one vertex in D. Example 1.26 Total Dominating Number The total dominating number is the minimum cardinality of a total dominating set. Here, rt(G)=4 CHAPTER-2 Maximal and Minimal Dominations in Digraphs Maximal Domination and Maximal Total Domination in Digraphs Let D = (V, A) is a finite, directed graph without loops and multiple arcs (but of opposite arcs are allowed) and G = (V, E) is an finite, undirected graph without loops and multiple edges. Definition 2.1: A set S of vertices in a graph G = (V, E) is a dominating set if every vertex in V-S is adjacent to at least one vertex in S. The minimum cardinality of a dominating set of G is called the domination number of G and is denoted by . Definition 2.2: A set S of vertices of a graph G is a maximal dominating set if S is a dominating set and V-S is not dominating set. The minimum cardinality of a maximal dominating set of G is called the maximal domination number of G and is denoted by . Definition 2.3: Let G = (V, E) be a graph without isolated vertices. A dominating set S of V is a total dominating set of G if the induced subgraph has no isolated vertices. The minimum cardinality of a total dominating set of G is called the total domination number of G and is denoted by . Definition 2.4: A total dominating set S of a graph G is a maximal total dominating set if V-S is not dominating set of G. The minimum cardinality of a maximal total dominating set of G is called the maximal total domination number of G and is denoted by . Definition 2.5: A set S of vertices in a digraph D = (V, A) is a dominating set if for every vertex u in V-S, there exists a vertex v in S such that . The domination number of D is the minimum cardinality of a dominating set of D. Definition 2.6: Let D = (V, A) be a digraph in which for all . A subset S of V is called a total dominating set of D if S is a dominating set of D and the induced subgraph has no isolated vertices. The total domination number of D is the minimum cardinality of a total dominating set of D. Definition 2.7: A dominating set S of a digraph D= (V, A) is a maximal dominating set if V-S is not a dominating set of D. The maximal domination number of a digraph D is the minimum cardinality of a maximal dominating set. Definition 2.8: A dominating set S of a digraph D is minimal if for each vertex is not a dominating set of D. is a minimal dominating set is not a dominating set Therefore, is a maximal dominating set, Theorem 2.1: If a digraph D contains an isolated vertex, then a minimal dominating set S of D is a maximal dominating set. Proof: Let v be an isolated vertex of D. Then v is in every dominating set S of D. Thus V-S is not a dominating set of D. This proves the result. The converse of the above theorem is not true always. Theorem 2.2: For any digraph D, . Proof: Clearly, every maximal dominating set of a digraph D is a dominating of D. Hence holds. Result 2.1: For a directed path with vertices, Result 2.2: For any directed path with vertices, . Result 2.3: For a directed cycle with vertices, Result 2.4: For any directed cycle with vertices, . Definition 2.9: A total dominating set S of a digraph D= (V, A) is a maximal total dominating set if V-S is not a total dominating set of D. The maximal total domination number of a digraph D is the minimum cardinality of a maximal total dominating set of D. Definition 2.10: A total dominating set S of a digraph D is minimal if for each vertex is not a total dominating set of D. Definition 2.11: For the direct cycle as show in figure, is a minimal total dominating set is not a total dominating set Therefore, is a maximal dominating set Clearly, . Theorem 2.3: For any digraph D without isolated vertices, . Proof: Every maximal total dominating set of a digraph D is a total dominating set of D. Thus holds. A is a minimum total dominating set. Theorem 2.4: For a directed path with vertices,. Proof: Let S be a of . Then . Clearly V-S does not contain a total dominating set. Thus . Theorem 2.5: For a directed cycle with vertices,. Proof: Let S be a of . Then . Clearly V-S does not contain a total dominating set. Hence . Theorem 2.6: For any digraph D with and with an end vertex v such that id(v) = 1, . Proof: Let v be an endvertex of a digraph D such that id(v) = 1 and S be a of D. Then and is a successor of some vertex in S. Thus v is an isolated vertex in . Hence S is a of D. Thus holds. Minimal Dominating Sets in Digraphs Definition 2.12: A directed graph (digraph) is a pair G = (V, A), where V is a set of nodes and is a set of arcs, i.e., ordered pairs of nodes. We say that node u dominates node v (or node v is dominated by node u) if arc (u, v) is in G. Arc (u, v) is denoted as u→v graphically. Definition 2.13: In digraph G, the indegree of node v is the number of arcs directed into v and is denoted as , i.e., . Definition 2.14: The outdegree of node u is the number of arcs going out of u and is denoted as , i.e., . Definition 2.15: In digraph G = (V, A), a set of nodes S V is a dominating set of G if each node S is dominated by at least a node in S. Definition 2.16: A minimal dominating set Sm is a dominating set with no proper subset of Sm as a dominating set. Definition 2.17: Suppose that u is a node of dominating set S. Node u is called redundant if S-u = S-{u} is still a dominating set. Definition 2.18: A minimum dominating set SM is a dominating set of minimum cardinality. Definition 2.19: The cardinality of a minimum dominating set is called the domination number of G and is denoted by γ(G). The following theorem shows the construction of a minimal dominating set incrementally. Notation: When a new arc is added into G, the new graphs is denoted by . When an arc is denoted from G, the new graphs is denoted by . Lemma 2.1: Suppose and be a minimal dominating set of G = (V,A) and reapectively. If , then (1) is a dominating set of G. (2) S is a minimal dominating set of if S is a dominating set of . Proof: Since is a dominating set of and , holds. The above equation means that dominates each node of in G.Thus, is a dominating set of G by the definition of dominating set. Otherwise, S is a dominating set but not a minimal dominating set of . Then S-{s} is still a dominating set of for certain node . Consequently, S-{s} is a dominating of G by lemma 4.1 (1), which is contradictory to the hypothesis that S is a minimal dominating set of G. Roughly, Lemma 4.1(1) indicates that a minimal dominating set of G+e is very similar to a minimal dominating set of G and can be generated from it cheaply. In fact, as indicated in Theorem 4.1 afterwards, there exist S and S+e, minimal dominating sets of G and G+e respectively, such that holds. However, this property does not hold for the minimal dominating sets of G and G-f . That is, given a minimal dominating set S of G, there may not exist a minimal dominating set S-f of G-f that is close to S in size. The following theorem explains the construction of a minimal dominating set of G+e from a minimal dominating set of G. Theorem 2.6: Let S be a minimal dominating set of G = (V, A) and suppose that where . Then Proof: Let S be a minimal dominating set of G = (V, A) and . Since G G+e and according to Lemma 4.1(1), S is a dominating set of G+e. To derive a minimal dominating set of G+e from S, we have the following two cases: (1) and (2) . Case 1: If , we will claim that S is a minimal dominating set of G+e by the definition of a minimal dominating set. Since S is a minimal dominating set of G, then for each there exists node such that w cannot be dominated by any nodes of in G. Since no new arcs from is inserted considering that e = (x, y) and , this node w cannot be dominated by any nodes of in G+e either. Therefore, S is a minimal dominating set of G+e from the definition of a minimal dominating set. Therefore, for a given minimal dominating set S of G = (V, A) and arc , the above proved that S is a minimal dominating set of G+e if . Case 2: If , we will claim that S may not be a minimal dominating set of G+e. To derive a minimal dominating set of G+e from S under this situation, we need to consider the two subcases: (i) and (ii) . Subcase (i): If nodes x; y 2 S, the insertion of e might make y redundant only if each node of can be dominated by a node of . That is, ................(1) Where . Moreover, if S-y is a dominating set but not a minimal dominating set of G+e, then there exists such that is a dominating set of G+e. This will result in being a dominating set of G which is contradictory to the fact that S is a minimal dominating set of G. Therefore, is a minimal dominating set of G+e. Similarly, it can be proven that S is a minimal dominating set of G+e if Formula (1) does not hold. Subcase (ii): If node but node , the insertion of e might cause a node that dominates node y in G to be redundant. Let .. A node is redundant if the following formula holds: ...(2) That is, each node that dominated by u is also dominated by other node in S. It should be noted that such node u is unique if it exists (otherwise, it will be contradictory to the assumption that S is minimal). In this situation, it can be proven that is a minimal dominating set of G+e. Similarly, if there does not exist such node u satisfying Formula (2), it can be proven that S is a minimal dominating set of G+e as each such that is not redundant in G+e. Note: The above result says that, for any given minimal dominating set S of G, there exists a minimal dominating set S+e of G+e such that S+e can be derived by removing at most one node from S. That is, ..............(3) holds for a node and S+e can be set to S if e = (x, y) is in . To use Theorem 1 on inserting a set of arcs I, a straightforward way is to divide I into two disjoint subsets I1 and I2; I1 is the subset of I where for each arc (x, y) in I and I2 is the set of the rest arcs of I. By Theorem 1, S, the minimal dominating set of G, is a minimal dominating set of . Thus, a minimal dominating set S+I of G+I can be constructed from S and rather than scratch built from S and G. This strategy can be more efficient on generating a minimal dominating set of G+I as some operations on the arcs of I2 can be avoided. The following theorem gives the construction of a minimal dominating set decrementally. Theorem 2.8: Let S be a minimal dominating set of G = (V, A) and . Let denote and Then Is a minimal dominating set of . Proof: Let S be a minimal dominating set of G = (V, A) and . As indicated in Figure 1, a minimal dominating set of G-f can be very different from S. However, since it can easily prove that is a dominating set of G-f , a minimal dominating set of G-f can be derivable from and may require the removal of many S nodes. Below is the detailed explanation. (1) S is a minimal dominating set of G-f if . In this situation, S is a dominating set of G-f as each node of V-S is still dominated by a node of S in G-f . Moreover, since and according to Lemma 4.1(2), S is a minimal dominating set of G-f . (2) Otherwise, S may not be a minimal dominating set of G-f if . In this situation, the deletion of f = (x, y) requires node y to be added into S if node y is not dominated by S in G-f any more. Sequentially, this may result in some other nodes of S to become redundant. Specifically, from Lemma 4.1(2), S is a minimal dominating set of G-f if ...............(4) Holds for . Or else, is a dominating of but not be a minimal. In order to derive a minimal dominating set from , some redundant nodes of in need to be removed. In the following, we show that a minimal dominating set of can be derived in terms of arcs insertion through using Theorem 4.1. Let where . It can be proven that is a minimal dominating set of . Therefore, a minimal dominating set of G-f can be derived from through repeatedly inserting an arc of (i) and (ii) into . Thus, according to Theorem 4.1, a redundant node of in can only be a node of , ......................(5) ....(6) Result 2.5: Let G = (V, A) be a digraph and and . Then , . Proof: Clearly, first equation as each dominating set of is a dominating set of G, Consequently, is a dominating set of . By theorem 4.1, it derives that holds. Again from theorem 1, it derives that or holds. CHAPTER-3 Inverse Domination and Inverse Total Domination in Digraphs Let D = (V, A) is a finite, directed graph with neither loops nor multiple arcs (but pairs opposite arcs are allowed ) and G = (V, E) is a finite , undirected graph with neither loops nor multiple edges. Definition 3.1: Let D = (V, A) be a digraph. Let S be a minimum dominating set in a digraph D. If V–S contains a dominating set of D, then is called an inverse dominating set with respect to S. The minimum cardinality of an inverse dominating set of a digraph D is called the inverse domination number of D and is denoted by (D). Example: Digraph D is a minimum dominating set and is not a dominating set. Thus V-S does not contain a dominating set. Hence the digraph D has no an inverse dominating set. Definition 3.2: The upper inverse domination number of a digraph D is the maximum cardinality of an inverse dominating set of D. Example: Digraph D The minimum dominating sets of D are and the corresponding inverse dominating sets are respectively. Thus and =2. Hence . Example: Digraph D The only minimum dominating sets of D is and the corresponding inverse dominating sets is . Therefore and =3. Hence . Result 3.1: For any directed cycle Result 3.2: If a graph D has -set, then and this bound is sharp. Proof: Clearly every inverse dominating set of a digraph is a dominating set. Thus holds. Result 3.3: If a graph D has -set, then and this bound is sharp. Proof: The result 3.2 follows from the definition of . Definition 3.3: Let D = (V, A) be a digraph which id(v) + od(v) for all . Let S be a minimum total dominating set in a digraph D. If V-S contains a total dominating set of D, then is called an inverse total dominating set with respect to S. The inverse total domination number of D is the minimum cardinality of an inverse total dominating set of D. Definition3.4: The upper inverse total domination number of a digraph D is the maximum cardinality of an inverse total dominating set of D. Digraph D The minimum total dominating sets of D are and and the corresponding inverse total dominating sets are and respectively . Therefore A -set is a minimum inverse total dominating set of a digraph D. Not all digraphs without isolated vertices have a total dominating set. We also note that not all digraphs without isolated vertices have an inverse total dominating set. For example, the directed cycle C4 has a total dominating set, but has no an inverse total dominating set. Result 3.4: If a digraph D has a –set, then and this bound is sharp. Proof: Clearly, every inverse total dominating set is a total dominating set. Thus holds. The digraph D of the above figure achieves this bound. Result 3.5: If a digraph D has a –set, then and this bound is sharp. Proof: follows from the definition of . The digraph D of the above figure achieves this bound. Result 3.6: Let S be a -set of a connected digraph D. if a –set exists in D, then D has at least 4 vertices. Proof: Let S be a -set of D. Since D has no isolated vertices, . If a -set exists, then V – S contains a total dominating set with respect to D. Thus . Thus D has at least 4 vertices. Result 3.7: If a digraph D has a –set, then . Proof: By definition , and by result 5.4, Thus . By result 5.5 Since . Hence the proof. CHAPTER-5 Domination Number of Digraphs Definition 5.1: A digraph in which every vertex has indegree one is called contrafunctional digraph. Definition 5.2: A vertex v of a digraph D is called a source of D if every vertex is reachable from v. Definition 5.3: A tree from a vertex (or arborescence) is a digraph with a source but with no semicycles. Definition 5.4: A (directed ) star Sn is a digraph on n vertices consisting of a center v and a set of arcs from . Theorem 5.1: Let D be a digraph with order n and minimum indegree . Then D has a dominating set of size at most Proof: Fix p with . Let us select, randomly and independently each vertex of V = V(D) with probability p. Let S be the random set of all vertices selected, and let T be the random set of all vertices not in S that do not have any in-neighbors in S. Then the expectation of the random variable is since has a binomial distribution with parameter n and p. To find , we have , where if and otherwise. Note that For each . Thus, we have Therefore, we have ……….(1) Then the minimum value of it is Which is attained when This means that there is at least one choice of S such that . The set is clearly a dominating set of D whose cardinality is at most Theorem 5.2: Let D be a digraph with order n and minimum indegree 1. Then, we have 1 n. Proof: Let D has a vds-cover H, namely, take H as the empty digraph on V (D). Among all such vds-covers of D, let H* be one with minimum number of copies of S1. For each k = 1,2,..., let Hk* be the subdigraph of H* consisting of weak components that are isomorphic to Sk and let hk denote the number of weak components in Hk*. First, the subdigraph of D induced by V(H1*) has no arcs at all since otherwise, H* violates the minimality. Next, there are no arcs of D from vertices in Hk* to vertices in H1* because if not, H* violates the minimality also. However, each vertex in H1* is the terminal vertex of at least arcs. Hence these arcs must be incident from vertices in H2*. Let uv be a star in H2* with center u. Then, because of the minimality of H*, u is not adjacent to any vertex in H1* and v is adjacent to at most one vertex in H1*. Since each vertex in H1* has indegree at least , we have h2 h1. Now let S be the set of all centers of the stars in H*. Then S is a dominating set of D and Corollary5.1: Let D be a weak contrafunctional digraph. Then we have the following: (1) γ(D) = ǀVǀ iff D = C3 (2) γ(D) < ǀVǀ iff D ≠ C3 Here, C3 denotes a directed 3-cycle. Proof: (1) The sufficiency is trivial. For the necessity, first note that for integer n ≥ 2, n ≤ iff n = 3. Suppose that γ(D) = ǀVǀ. then γ(D) = ǀVǀ ≤ by corollary and so ǀVǀ = 3 by the note. Moreover, C3 is the only digraph on 3 vertices whose domination number is 2. This completes the proof of the first part. (2) Since a weak contrafunctional digraph D has = 1, we have γ(D) ≤ ǀVǀ by theorem and so the second part follows. Theorem 5.3: Let D be a contrafunctional digraph. Then we have the following: (1) γ(D) = ǀVǀ if and only if D is a disjoint union of 3-cycles. (2) γ(D) < ǀVǀ if and only if D is not a disjoint union of 3-cycles. Proof: (1) The sufficiency is trivial. To prove the necessity, let γ(D) = ǀVǀ and let{H1,H2,…Hl} be the set of weak components of D. Suppose that there exist. Then we have ǀVǀ = γ(D) = < = ǀVǀ, which is a contradiction. Thus every weak component of D is a 3-cycle and hence D is a disjoint union of 3-cycles. (2) Suppose that D is not a disjoint union of 3-cycles and let{H1,H2,…Hl} be the set of weak components of D. Then all Hi's are weak contrafunctional digraphs, and Hi ≠ C3 for some i. Hence γ(D) = < = ǀVǀ and so the sufficiency has been established. To prove the necessity, we let γ(D) < ǀVǀ and assume that D is a disjoint union of 3-cycle Zi. Then, we have which contradicts γ(D) < ǀVǀ. Therefore D is not a disjoint union of 3-cycles. Thorem5.4: Let D be a weak digraph with minimum indegree = 1 and Let ǀV(D)ǀ = n. Then we have the following: (1) . (2) . (3) . moreover, all bounds are sharp. Proof: Since (2) and (3) are the same as Theorem 6, it suces to prove (1). For each vertex in D, color one incoming arc green and the others red and next choose only green arcs. Then we have a spanning contrafunctional subdigraph H of D. First, consider the case that H is not a disjoint union of 3-cycles. Clearly,(D) ≤ (H) < n By theorem 8 and hence (D)