HIKHHIWM \ a lllilWlUlHWNIHHIWIW| 028 _| I IUD lllllllllllllllllllllllllllllilllll||||||||ll||||||llllllllllll 1329301020152 This is to certify that the dissertation entitled ON THE DOMINATION NUMBER OF A DIGRAPH presented by Changwoo Lee has been accepted towards fulfillment of the requirements for Ph.D. degree in Mathematics 164/217” Major professor Date /i @677 /744/ MSU is an Affirmative Action/Equal Opportunity Institution 0-12771 LIBRARY Michigan State Unlverslty PLACE IN RETURN BOX to remove this checkout from your record. To AVOID FINES return on or before date due. LI IL__I :-__I[: , I [II I I_IE3LI I -I IS J II I MSU Io An Affirmative Action/Equal OpportunIty Institution W ”39.1 ON THE DOMINATION NUMBER OF A DIGRAPH By Changwoo Lee A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the Degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1994 ABSTRACT ON THE DOMINATION NUMBER OF A DIGRAPH BY Changwoo Lee A subset S of vertices of a digraph D is a dominating set of D if every vertex not in S is adjacent from a vertex in S, and the domination number of D is the number of vertices in any smallest dominating set of D. A subset I of vertices of D is an independent set of D if no two vertices of I are joined by an arc in D. The independence number of D is the number of vertices in any largest independent subset of vertices of D. If D has an independent and dominating set, the independent domination number of D is the number of vertices in any smallest independent and dominating subset of vertices of D. We first establish bounds for the domination numbers of various types of digraphs and determine the domination number of a random digraph. Next we study the relations among the domination number, the independent dom- ination number, and the independence number of an oriented tree and a binary tree, respectively, and we estimate their bounds. We then derive a formula for the ex- pected independent domination number of random binary trees and determine the asymptotic behavior of the expectation. Finally we establish bounds for the domination number of tournaments and the Paley tournament, and we determine the domination number of a random tourna- ment. DEDICATION To my academic father, Edgar M. Palmer, for his sixtieth birthday iii ACKNOWLEDGEMENTS It is a great pleasure to thank my thesis advisor, Professor Edgar M. Palmer. His guidance, patience, understanding, and encouragement have been major factors contributing to this work. I would like to thank Professor Bruce E. Sagan for his introducing me to combinatorics as well as for his instruction and help. I also thank Professor David E. Blair, Professor Wei-Eihn Kuan, and Professor Jacob Plotkin for their time and advice. I owe special thanks to Stephen T. Hedetniemi, who sent me about fifty of his articles on domination theory, and to Robert W. Robinson, who made numerous helpful comments. iV Contents LIST OF TABLES vii Introduction 1 1 Digraphs 5 1.1 Definitions and Preliminary Results ................... 5 1.2 The Domination Number of a Digraph ................. 7 1.3 The Domination Number of a Random Digraph ............ I7 2 Oriented Trees 29 2.1 The Domination Number of an Oriented Tree ............. 29 2.2 The Domination Number of a Binary Tree ............... 32 2.3 The Expected Independent Domination Number of Random Binary Trees .................................... 36 3 Tournaments 46 3.1 The Domination Number of a Tournament ............... 46 3.2 The Domination Number of a Random Tournament and the Paley Tournament ................................ 50 V Open Problems BIBLIOGRAPHY Vi 55 58 List of Tables 1.1 Constants in upper bounds for domination number 2.1 Values of ,a(2n +1) and u(2n +1)/(2n +1) . . . . vii Introduction The earliest ideas of dominating sets, it would seem, date back to the origin of the game of chess, in which one studies sets of chess pieces that cover or dominate various opposing pieces or various squares of the chess board [HeL90(a)]. In more recent time, dominating concepts were raised in the form of the Five Queens Problem by Kbnig in 1936 [K036]. Finally the topic of domination was given formal mathematical definition in the books by Berge [B658] in 1958 and Ore [Or62] in 1962. But relatively little had been done on this topic until Cockayne and Hedetniemi published a survey article [CoH77] in 1977. Since then over 500 papers have been published on the subject (see, for example, [HeL90(b)]). Among them there are many about the domination of undirected graphs but almost nothing for the domination number of directed graphs. In this thesis we will develop theory for the domination number of directed graphs. In his book [Or62], which is the first graph theory book written in English, O. Ore says that a graph G = (V,E) with no isolated vertices has domination number at most %|V|. W. McCuaig and B. Shepherd lowered this upper bound of the domination number to §|V| for connected graphs with minimum degree at least 2 except for seven specific graphs [McS89]. B. Reed lowered it to glVl for graphs with minimum degree at least 3 [Re9x]. Moreover, using an elegant application of the probabilistic method, N. Alon and J. Spencer [A1892] proved that any graph with minimum degree 6 has domination number at most figfiiillll/l. However, there has been no corresponding study of the domination number for digraphs. I The main goal of this thesis is to study the domination number for various types of digraphs and random digraphs. We first establish an upper bound for the domination number of digraphs with minimum indegree 6' at least one by applying the probabilistic method. This bound is good for large 6’ but quite loose for small 6‘. Finding a vertex disjoint star cover of D, we determine a sharp upper bound for the case 6‘ = 1. We then determine the domination number of a random digraph using the first and the second moment methods. The domination number of a random digraph turns out to be one of two consecutive numbers. Next, we study the relations among the domination number, the independent domination number, and the independence number of an oriented tree and a binary tree, respectively, and we determine bounds. We then derive a formula for the ex- pected value of the independent domination numbers of random binary trees and find the asymptotic behavior of the expectation. Finally, using an algorithmic method, we establish an upper bound for the dom- ination number of tournaments, which is a function of the number of vertices. To investigate the sharpness of this bound, we first find the domination number of a random tournament which is also one of the two consecutive numbers and next find bounds for the domination number of the Paley tournament, which is a typical quasi- random tournament. Here are some of the basic definitions we need from graph theory. Those not included may be found in the books [B085], [HaNoC65], and [Pa85]. A directed graph (or digraph) D consists of a finite set of vertices, V(D), together with a set of arcs, E(D), which are ordered pairs of vertices. Usually an arc (u,v) is denoted by no. The cardinality of V(D) is the order of D and the cardinality of E(D) is the size of D. We will use the convention that n = |V(D)|. If a = uv is an arc of a digraph D, then u is said to be the initial vertex of a and v the terminal vertex of a. We also say that a is an outgoing are from u and that a is an incoming arc to 2). We further say that a is incident from u and that a is incident to v, while u is incident to a and v is incident from a. Moreover, it is said to be adjacent to v and v is adjacent from u. The outdegree odD(v) of a vertex v in a digraph D is the number of vertices of D that are adjacent from v, and the indegree idD(v) of v is the number of vertices of D adjacent to v. The minimum indegree (or outdegree) of a digraph D, denoted 6“(D) (or (V(D)), is the minimum indegree (or outdegree) of a vertex in D, respectively. The open in-neighborhood of a set S Q V(D) is defined by N5(S') 2 {v E V(D) — S | v is adjacent to some it E S } and the open out-neighborhood of a set S Q V(D) is defined by NE(S) = {v E V(D) — S | v is adjacent from some it E S }, while the closed in-neighborhood of a set S (_I V(D) is defined by N5 [S] = N5(S) U S and the closed out-neighborhood of a set S Q V(D) is defined by NEW] 2 NETS) U S. A walk in a digraph D is a sequence vl,u2,...,vm of vertices such that v,- is adjacent to vi+1 for i = l to m — 1. If v1 = vm, the walk is called closed. A path in D is a walk in which no vertex is repeated. If there is a path from u to u, then 2) is said to be reachable from u. The length of a path is the number of arcs in it. The distance between two vertices is the length of any shortest path between them. A cycle is a walk with at least two vertices in which the first and the last vertices are the only ones repeated. We denote a cycle of order m by Cm and a path of order m by Pm. Each walk is directed from the first vertex to the last vertex. We also need a concept which does not have this property of direction and is analogous to a walk in a graph. A semiwalk is again a sequence '01, v2, . . .,vm of vertices, but either 22,--122, or vim--1 is an arc for i = 2,. .. ,m. A semipath, semicycle, and so forth, are defined as expected. A digraph D is strong if every two vertices are mutually reachable and D is unilateral if for any two vertices at least one is reachable from the other. We say that D is weak if every two vertices are joined by a semipath. A digraph is disconnected if it is not even weak. A subdigraph H of a digraph D is a digraph such that V(H) Q V(D) and E(H) is a subset of those arcs in E(D) that are incident with only the vertices in V(H). The subdigraph H of D induced by a set S <_: V(D) is a subdigraph such that if u, v E V(H) and uv is an arc of D then uv is also an arc of H. For a set S Q V(D), D[S] will represent the subdigraph of D induced by S. A subdigraph H of D spans D if V(H) = V(D). A maximal, weak subdigraph of D is called a weak component of D. Let {an} and {bu} be sequences of real numbers. Then an —-+ L means limnnoo an = L. The big-O and little-o notation is defined as usual: an 2 0(bn) means that there are constants K and N such that Ianl g K|bn| for all n > N, and an 2 0(bn) means limnnoo Ian/bn| = 0. If an 2 (1 + 0(1))bn, we say that an and bn are asymptotically equivalent and we write an N bn. We use [ch to denote the greatest integer that is at most 3:, while [:13] denotes the least integer that is at least :13. For any positive integer n, [n] denotes the set {1, 2, - - - ,n}. For any number n and positive integer k, < n >k denotes the falling factorial < n >k= n(n — 1)--- (n — k +1) and < n >0: 1 for any n. Chapter 1 Digraphs 1.1 Definitions and Preliminary Results Let D be a digraph of order n. A subset S of V(D) is a dominating set of D if for each vertex v not in S there exists a vertex u in S such that (u,v) is an arc of D. Note that V(D) itself is a dominating set of D. A minimal dominating set is a dominating set such that no proper subset dominates. A dominating set having smallest cardinality among all dominating sets of a given digraph D is called a minimum dominating set of D. The cardinality of a minimum dominating set of D is the domination number of D. We will reserve a(D) or just a for the domination number of D. For example, it is easily seen that 01(Pn) = [g] and a(Cn) = [g] by choosing every other vertex for a minimum dominating set. Note that if we add a new arc to a digraph D, then the domination number of the resulting digraph is at most that of D and that if we remove an arc of a given digraph D, then the domination number of the resulting digraph is at least that of D. For subsets S and T of V(D), we say that S dominates T if S is a dominating set of D[S U T]. For an undirected graph G, a subset S of V(G) is a dominating set of G if for every vertex v not in S there exists a vertex u in S such that {u, v} is an edge of G. The domination number of G is the minimum cardinality of all dominating sets of G. 5 A minimal dominating set of G, a minimum dominating set of G, and so forth, are defined as expected. We are now ready to state some results in [Or62]. Theorem 1.1.1 ([Or62]) Let G be a directed or undirected graph. A dominating set S is a minimal dominating set if and only iffor each vertex v in S one of the two following conditions holds: (1) v is not adjacent from any vertex in S. (2) There exists a vertex u not in S such that v is the only vertex in S adjacent ton.- Theorem 1.1.2 ([Or62]) Any undirected graph G without isolated vertices has a dominating set S such that its complement S is also a dominating set. Proof: Let S be a minimal dominating set of G. Every vertex in S must be adjacent to some vertex in S, or S would not be minimal. Thus S is also a dominating set. I This theorem implies that any undirected graph of order n without isolated ver- tices has domination number at most 17. / 2. However, the corresponding theorem for digraphs does not hold as we can see, for example, in the case of a directed 3-cycle. A set S of vertices of an undirected graph G is called an independent set of G if there are no edges between any of its vertices. The independence number of G, denoted ,8(G), is the maximum cardinality taken over all independent sets of G. An independent set and the independence number of a directed graph are defined analogously. Now we state a useful theorem relating the domination number of a graph G to the independence number of G. Theorem 1.1.3 ([Or62]) An independent set of an undirected graph G is maximal if and only if it is a dominating set. I This theorem implies that a(G) _<_ 6(G) for undirected graphs G. For directed graphs, however, it does not hold. A directed 3-cycle is an example. 1.2 The Domination Number of a Digraph In this section we will establish bounds for the domination number of digraphs with minimum indegree at least one. In a graph, every isolated vertex must belong to any dominating set. Similarly, in a digraph, every vertex with indegree zero must belong to any dominating set. Therefore, it is quite natural to concentrate on digraphs with minimum indegree at least one. Let X be a random variable on a probability space (I, and let E [X] be the ex- pectation of X. Then we know that if E[X] g c for some constant c, there is an s E it such that X(s) S c. Let X1,X2,...,X,, be random variables, and let X = c1X1 + - - - + Can, where ci’s are constants. Linearity of expectation states that E[X] = c1E[X1] + + an[Xn]. The power of this property comes from the fact that there are no restrictions on the dependence or independence of the Xi’s. Using these simple observations, we prove the following theorem. Theorem 1.2.1 Let D be a digraph with order n and minimum indegree 6‘ Z I. Then D has a dominating set of size at most {1—(1j,_)t—+< 1 Han. Proof: Fix p with 0 < p < I. Let us select, randomly and independently, each vertex in 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 E [IS I] of the random variable IS I is E [IS I] = np since IS I has a binomial distribution with parameters n and p. To find E [ITI], we let ITI = ZUEV Xv) where Xv = I if v E T and Xv = 0 otherwise. Note that P(v E T) = P(v and its in—neighbors are not in S) _ (1 _ p)1-I-id(v) 3(1-er for each v E V. Thus, we have EWH=MZMFXWM] vEV UEV = Z P(v E T) g n(l — p)1+6-. vEV Therefore, we have EWfl+fltSnP+M1-MHV- (LU Using elementary calculus, we minimize the right side of (1.1) with respect to p. Then the minimum value of it is I 1 1 1+6— {1_(1+6— )6_—}na which is attained when 1 )f3. 1 + 5‘ p=1—( This means that there is at least one choice of S such that 1 m 1 fl 1+siilli+sjé }” |S|+|T|S{1—( The set S U T is clearly a dominating set of D whose cardinality is at most I 1 1 1+6— 1+6“ U—( This theorem gives us a good upper bound for the domination number of a digraph with large minimum indegree. The coefficient of this upper bound goes to zero when the minimum indegree 6— goes to infinity. See Table (1.1). Table 1.1: Constants in upper bounds for domination number 5—0.5 “statuary—>1? I.“ 1 .7500 .5000 .6666 2 .6150 .5643 .6000 3 .5275 .5246 .5714 4 .4650 .4772 .5555 5 .4176 .4349 .5454 6 .3802 .3988 .5384 7 .3498 .3682 .5333 8 .3245 .3421 .5294 9 .3031 .3197 .5263 10 .2847 .3002 .5238 102 .0545 .0554 .5024 103 .0078 .0078 .5002 104 .0010 .0010 .5000 Remark: Let G be an undirected graph with order n and minimum degree 6. Then, using the same argument as in Theorem 1.2.1, we can show that the domination number of G is at most >%+(#)1—‘E—“}n. (1.2) {1_( 1+6 1 + 6 L. Lovasz showed in [L075] that the domination number of G is at most l+ln6 1+ 6 n, (1.3) and N. Alon and J. Spencer found a similar upper bound 1 l 6 l + “( + )n (1.4) 1+6 10 (see [A1392]). It is easily checked that these three upper bounds for the domination number of an undirected graph are asymptotically the same but our result (1.2) is smaller than (1.3) and (1.4) for 6 Z 4. See Table (1.1). It is easy to see that the domination number of a digraph D is the sum of the domination numbers of all weak components of D. But note that this is not true for unilateral or strong components. Since every vertex of indegree zero must belong to any dominating set, we consider weak digraphs with minimum indegree at least one. Then, what is the domination number of a digraph in which every vertex has indegree one? Such a digraph is called a contrafunctional digraph. A vertex v of a digraph D is called a source of D if every vertex is reachable from v, and a tree from a vertex (or arborescence) is a digraph with a source but with no semicycles. A (directed) star S1, is a digraph on n vertices consisting of a center v and a set of arcs from v to V(Sn) — {v}. Lemma 1.2.2 ([HaNoC65]) A weak digraph is a tree from a vertex if and only if exactly one vertex has indegree zero and every other vertex has indegree one. I We need the above lemma to prove the following. Theorem 1.2.3 Every tree T from a vertex v has domination number I 1 3 am 3 I§|V(T)II- Moreover, the bounds are sharp. Proof: We shall state an algorithm which finds a dominating set for a tree T from a vertex v. This algorithm begins by selecting a largest star that is the farthest from the source v. Then we put the center of the star into a dominating set. Next we 11 remove the vertices in the star from T to get a new tree from a vertex and repeat this process. Algorithm: Let T1 = T be the given tree from the vertex v, and let S0 = (t. Put i = 1 and go to (I). (1) Take a vertex v,- with maximum distance from v in T,. (2) If v, = v, then let S = Si_1 U {v} and stop. If v, 7é v (i.e., idT,(v,-) = I), let u,- be the vertex of T,- that is adjacent to v,- and go to (3). (3) If odT,(u,-) = 1 and u,- = v, then let S = Si-1 U {u,-} and stop. If odT,(u,-) = 1 and u.- 7t v, then let S,- = S,_1 U {ui} and T,“ = T,- — {u,-,v,-} and next return to (1) putting i = i + 1. If odT,(u,-) 2 2, go to (4). (4) If u,- = v, then let S = S;_1 U {v} and stop. If u,- 79 v, then let S,- = S,_1 U {ui} and TH] = T,- — N+[u,-], and next return to (1) putting i = i + 1. From this algorithm, it is easily seen that S is a dominating set for T and that ISI S I§IV(T)I] since in each step except (possibly) the last, we take at least two vertices and put only one vertex into S that dominates the rest of them. Extremal digraphs are a star Sn on n vertices and a path Pn on n vertices. I Here we note that the complexity of this algorithm is 0(n2), where n = IV(T)I. Lemma 1.2.4 ([HaNoC65]) The following statements are equivalent for a weak digraph D. (1) D is contrafunctional. (2) D has exactly one cycle G and the removal of any one arc ofG results in a tree from a vertex. I The removal of any arc in a given digraph never decreases its domination num- ber. Therefore, combining Theorem 1.2.3 and Lemma 1.2.4, we have the following 12 corollary. Corollary 1.2.5 Every weak contrafunctional digraph D has domination number 1 1 S 0(D) S I§|V(D)|I- Moreover, the bounds are sharp. To see the latter, we construct a digraph D as follows. We add one new vertex u to a star Sn_1 and add two new arcs between u and the center of Sn_1. Then D is an extremal digraph, and a cycle 0,, will do for the other extreme. If a digraph D has a spanning subdigraph H of D such that H is a disjoint union of stars, then H is called a vertex disjoint star cover (vds-cover) of D. Theorem 1.2.6 Let D be a digraph with order n and minimum indegree 6‘ 2 I. Then we have lg a(D) 3 Proof: It is easy to see that 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 h = 1,2,..., let H}: be the subdigraph of H“ consisting of weak components that are isomorphic to S k and let hk denote the number of weak components in H 1:- The subdigraph of D induced by V(Hf) has no arcs from vertices in Uk¢3 H ,2" to vertices in Hf because otherwise, H * violates the minimality. However, each vertex in H i“ is the terminal vertex of at least 6‘ arcs. Hence these arcs must be incident from vertices in H;. Let uv be a star in H; with center it. Then, because of the minimality of H *, u is not adjacent to any vertex in Hi“ and v is adjacent to at most one vertex in Hf. Since each vertex in Hf has indegree at least 6‘, we have hz 2 6‘h1. 13 Now let S be the set of all centers of the stars in H *. Then S is a dominating set of D and ISI 2 2,21 hi. Note that 6'+l >I>I 26’+1_2 — z fori=3,4,...andthat 6‘+1 h2—6‘h1 — h =—> . 26‘+1(h1+2h2) (hl‘l' 2) 26"+1 _0 Since IV(D)I 2' n = Zihi, 2'21 wehave 6_+1 6—+1 6—-I-1, = h 2h h,- 26—+1” 26-+1(1+ 2”Zn-+12 £33 2 (h1+h2)+Zhi= ISI l 2'33 This theorem gives a better upper bound for the domination number of a digraph with 6“ = 1 or 2 than that of Theorem 1.2.1. See Table (1.1). Corollary 1.2.7 Let D be a weak contrafunctional digraph. Then we have the fol- lowing: (1) a(D) = gIVI if and only ifD 2 G3. (2) a(D) < §IVI if and only ifD 75 G3. Here, G3 denotes a directed 3-cycle. Proof:(1) The sufficiency is trivial. For the necessity, first note that for integer n 2 2, 3n _<_ I3] iff n = 3. Suppose that a(D) — 2IVI. Then §IVI = a(D) S I§IVII _ 5 by Corollary 1.2.5 and so IVI = 3 by the note. Moreover, G3 is the only digraph on 3 vertices whose domination number is 2. This completes the proof of the first part. 14 IVI ODIN (2) Since a weak contrafunctional digraph D has 6' = 1, we have a(D) _<_ by Theorem 1.2.6, and so the second part follows. I Theorem 1.2.8 Let D be a contrafunctional digraph. Then we have the following: (I) a(D) = §IVI if and only ifD is a disjoint union of 3—cycles. (2) a(D) < §IVI if and only ifD is not a disjoint union of 3—cycles. Proof: (1) The sufficiency is trivial. To prove the necessity, let a(D) = §IVI and let {H1, H2, - - - ,Hl} be the set of weak components of D. Suppose that there exists a component that is not a 3—cycle. Then by Corollary 1.2.7, we have 2 2 31V] = 0(1)): 20432) < Z: fill/(Hill = 31V], 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, - - . ,Hz} be the set of weak components of D. Then all H,’s are weak contrafunctional digraphs, and H.- # G3 for some i. Hence M) = Zulu) < ; §IV(H.)I = 2M ii and so the sufficiency has been established. To prove the necessity, we let a(D) < gIVI and assume D is a disjoint union of 3-cycle Zfs. Then we have which contradicts a(D) < §IVI. Therefore D is not a disjoint union of 3-cycles. I The bound in Theorem 1.2.6 can be sharpened for weak digraphs with 3k vertices as follows. 15 Theorem 1.2.9 Let D be a weak digraph with minimum indegree 6‘ = 1 and let IV(D)I = n. Then we have the following: (1)Ifn E 0 (mod 3) andn Z 6, then 1 S a(D) S %n — 1. (2) Ifn 51 (mod 3) and n 2 4, then I f a(D) g IZnI. (3) Ifn E 2 (mod 3) and n 2 2, then 1 S a(D) g Ign]. Moreover, all bounds are sharp. Proof: Since (2) and (3) are the same as Theorem 1.2.6, it suffices to prove (I). 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, a(D) _<_ a(H) < gn by Theorem 1.2.8 and hence a(D) S gn — 1. Next, consider the case that H is a disjoint union of 3-cycles. Since D is weak but H is not, the arc set E (D) of D consists of E (H) and some arcs not in H. In addition, if we add some arcs in E (D) — E(H) to H, then the resulting digraph has a strictly smaller domination number than that of H. Therefore, a(D) < a(H) = 2n and hence a(D) _<_ gn — I. 3 This completes the proof of (I). For the sharpness of the lower bound in all cases, we take a digraph D as follows: V(D) = {v1,v2, . . . ,vn}, E(D) = {222211, ’01’02,’01’U3,. ..,v1vn}. For an extremal digraph of the case (1), we define a digraph D as follows: Take a disjoint union of k 3-cycles Z1, Z2, . . . , Zk, and let v,- be a vertex in Z,- for each i. Add k — I new arcs vivl for i = 2,3,. . . , k, and let D be the resulting digraph. Next, for an extremal digraph of the case (2), we define a digraph as follows: Take a disjoint union of k 3-cycles Z1, Z2, . . . , Z. and a new vertex u. Let v,- be a vertex in Z,- for each 16 i. Add k new arcs via and let D be the resulting digraph. Finally, for an extremal digraph of the case (3), we define a digraph D as follows: Take a disjoint union of k 3-cycles Zfs and a 2—cycle 02. Let u be a vertex in 02 and v,- in Z,. Add k new arcs vgu and let D be the resulting digraph. I Every unilateral digraph has at most one vertex of indegree zero and at most one vertex of outdegree zero, while every strong digraph has the minimum indegree at least one and the minimun outdegree at least one. Therefore we do not need any more degree restrictions for unilateral or strong digraphs. Theorem 1.2.10 Every unilateral digraph D has I 1 3 am) 3 I§|V(D)II- Moreover, the bounds are sharp. Proof: Let D be a unilateral digraph. Then D has at least one source (p.99, [HaNoC65]). We consider a spanning tree T from the source. Then am) 3 aIT) s Iélvam = I%|V(D)II. Let Sn be a star with center u, and let v be another vertex in Sn. We construct a unilateral digraph D as follows: V(D) = V(Sn), E(D) = E(Sn) U {wu I w E V(Sn) - {u,v}}. Then D is an extremal unilateral digraph, and P7, will do for the other extreme. I Corollary 1.2.11 Every strong digraph D has 1 1 s 041?) s I§|V(D)|I- Moreover, the bounds are sharp. 17 Proof: Since every strong digraph is weak, it suffices to prove the sharpness of the bounds. Extremal digraphs are a symmetric star and a cycle. I 1.3 The Domination Number of a Random Di- graph In this section we will determine the domination number of a random digraph. To do this, we describe probability models commonly used in the study of random digraphs or random graphs and explain the first and the second moment methods. For each positive integer n and each number p with 0 < p < 1, the probability space Dnm of digraphs is defined as follows: Each point in the space is a digraph with vertex set V 2 {1, 2, . . . , n} having no loops or multiple arcs, and the probability of a given digraph D with l arcs is given by P(D) 2 p’(l —p)"(”—1)". In other words, each arc is present with probability p, independently of the presence or absence of other arcs. In particular, if p 2 1/2, then each digraph is assigned the same probability, namely I/Dn, where D7, is the total number of digraphs on V. On the other hand, the probability space gm, of graphs is defined analogously and so the probability of a given graph G with l edges is given by P(G) 2 p’(l — p)(3)_l. In the study of random digraphs (or graphs), we cannot conclude anything about individual digraphs but what we do study are properties of sets of digraphs. Let Q be a property of digraphs. If A is the set of digraphs of order n with property Q and the probability P(A) of A has limit I as n ——> 00, then we say almost all digraphs have property Q or a random digraph has property Q almost surely. We are studying a sequence of probability spaces and the limit of a sequence of probabilities. The first and the second moment methods are important tools from probabil- ity theory which are used frequently in the study of random digraphs (or graphs). 18 Suppose X is a nonnegative integer-valued random variable. Let E[X] denote the ex- pected value of X and let P(A) denote the probability of the event A. Then we have P(X Z l) S E[X] from Markov’s inequality. Thus if E[X] —+ 0, then P(X Z 1) —> 0 and therefore P(X 2 0) —> 1. On the other hand, if E[X] 75 0, then we have P(X 2 0) S E[XQI/EIX]2 — I from Chebyshev’s inequality. Thus E[Xz] ~ E[X]2 implies P(X 2 0) —> 0 and therefore P(X Z I) —> 1. In what follows log denotes the logarithm with base 1/(1 — p) and In denotes the logarithm with base e. K. Weber determined the domination number for almost all graphs as follows. Theorem 1.3.1 ([We81I) For p fixed, 0 < p < 1, a random graph Gn 6 gm, has domination number either Ik*] + 1 or Ik*] -+- 2 almost surely, where k’“ 2 log, n — 2 log, log, n + log,, logb e and log, denotes the logarithm with base b 2 Up. Using the same techniques as in [We8l] for analyzing the first and the second moments, we establish a similar result for digraphs. Theorem 1.3.2 Forp fixed, 0 < p < 1, a random digraph Dn E 13,”, has domination number either Ik*] + 1 or I16] + 2 almost surely, where k'“ 2 log n — 2 log log n + log log e and log denotes the logarithm with base I/(I — p). 19 Proof: Let X be a nonnegative random variable such that X (Dn) is the number of dominating k-sets in Dn for each Dn 6 DW. Since P(a fixed vertex v does not dominate another fixed vertex u) 2 l — p :2 q, we have P(a fixed k-set K Q V does not dominate a fixed vertex in V — K) :- qk and hence P(a fixed k-set of vertices is a dominating set) 2 (l — qk)"‘k. Therefore, we have Tl - _ u=#(k)=E[Xl= (k)(1-q")” k- (1.5) It is convenient to change the notation by setting q 2 I/r in (1.5), and we thus have a = (:)(1— r-kr-k. (1.6) Note that k n nk (n)k n (,I = 7&7 = (1+ 0(1))? (1.7) when k —> 00 and k2 2 o(n). Substituting (1.7) in (1.6) and applying Stirling’s formula for kl, we have u = (1+ «Wig—,1 when k —+ 00 with k2 2 o(n). By taking the In of both sides of (1.8), we get (1 — r-kr-k, (1.8) Inn 2 k-I—klnn—klnk—éln27r—élnk (1.9) +(n — k) ln(l -— r’k) + ln(1 + 0(1)) when k —> 00 with k2 2 o(n). The term ln(1 — r‘k) in (1.9) becomes ln(1 —r—k) 2 —————————— . (1.10) 20 Substituting (1.10) in (1.9) and rearranging, we have 11w=.klnn—nr-k—klnk+k—%lnk+0(1) (1.11) when k —> 00 with k2 2 o(n) and n 2 o(r2k). Converting In in (1.11) to log, we have logu 2 klogn — nr‘k log e — klog k + klog e — glog k + (9(1) (1.12) when k ——> 00 with k2 2 o(n) and n 2 o(er). Note that the function (1.8) is defined for integer k such that k —> 00 as n —> 00 and k2 2 o(n). But we may regard (1.8) as a function defined for any real number k such that k —> 00 as n —> 00 and k2 2 o(n). Let log log n k2 k“+eand 6: O( ). (1.13) log n Then k satisfies k —> 00, k2 2 o(n), and n 2 o(r2k) and thus it follows from the definition of k*, (1.12), and (1.13) that log u 2 (log n)2(1 — r") — 2(log n)(log log n) — k* log k* + O(log n) (1.14) Note that ——c 1 _ e—elnr 2 1— (1 — elnr + C(62)) 2 elnr—O(62) as e—>0. (1.15) Substituting (1.15) and the definition of k* in (1.14) and rearranging, we have log ,u 2 (ln r)(log n)2e — 3(log n)(log log n) + (9(log n) elogn —3loge+0( 2 (lnr)(log n)(loglogn){1 )}. (1.16) og log n log log n Therefore, we have f —00 if limsup—‘J—‘lgl < 3loge and e 2 0(M) n—+oo loglogn 108'” log}; —> < 00 if liminf—il-‘lg—TL— > 3loge and e 2 00351—053) ( n—+oo loglogn 108” 21 and thus ' 0 if limsuplflfln— < 3loge and e 2 (KM) n—+oo 08108” logn #--+< . . . l — 1 l L 00 1f llgglflsg?§:n > 3loge and e — O(——°fi)g°gn). It follows easily by observing the logarithmic derivative of the term (en/19V \/27T—k in (1.8) that if k —> 00 as n —> 00 and k2 2 o(n), then u is asymptotic to an increasing (1 _ r—k)'n—k function of k when n -—> 00. Hence, for any such real sequence k at all, we have ’ 0 if limsupW < 3loge K 00 if limian > 3log e. —k n—+oo 108108 Now, it is easy to see that 0 if kzIk*I WI 00 if k2 Ik*I+2. This means that for any k S Ik*], a random digraph has no dominating k-sets almost surely. We have shown that u 2 E[X] —> 00 for k 2 Ik*] + 2. Thus, using the second moment method, we want to show that P(X Z I) —+ 1 for k 2 Ik*] + 2. To do this, it suffices to show that E[Xz] ~ #2 for k 2 Ik*] + 2. Let us estimate E[X2] — #2 for k 2 I_k*I + 2. Let as be the number of ordered pairs (K, K') of k-sets of vertices with IK fl K’I 2 s, and let P, be the probability that two fixed k-sets K and K’ with IK fl K’I 2 s are dominating sets. Then k E[Xz] 2 Z asPs. 20 22 We want to estimate asPs up to the values of 3. Now we have three cases to consider. Case 1: Since ak denotes the number of k-subsets of vertices and Pk the probability that a fixed k-subset of vertices is a dominating set, it follows that akPk2u2o(u2) as u—>oo. Case 2: Since P0 S P(all vertices not in K U K’ are dominated by K and K’) = {(1 _ 7‘_k)2}n_2k and n n—k n 2 2 < :0 (III ,. I—Ik)’ wehave 0.0130 S (n>2(1—T—k (—n—2k) k 2 (2)2:4c1—T—k ”_k)(1—r_k)"2’° = #2(1+0(1)))62"”‘k 2 u2(1+o(1))(1+2kr"“) = u2(1+ OHM—’9)- Therefore, we have aoPo — H2 = #2OIk7‘_k) = 0042)- Gase 3: Let K and K’ be two fixed k-sets of vertices with IK fl K’I 2 s, 1 S s S k — 1, and let P(v) be the probability for afixed vertex v E V—(KUK’) :2 R to be dominated by both K and K’. Then P(v) 2 P((K (I K’ dominates v)V (both 23 sets K — S and K’ — S dominate v and K (I K’ does not dominate 12)). Thus P(v) = (1— 7‘”) + (l — r‘k+s)27~‘5 2 l— r‘2k(2rk — r3). Therefore, we have P, S P(both sets K and K’ dominate R) 2 (1— r—Zk(2r’c — rs))"—2k+s :2 b,. It is easily checked that a. = (2) (f) (I: : f) 5 (1+ 0(1)) (2)25: Let Cs : n—s(1 _ T_k)—2(n—k)k2s+lbs. Then, using (1.17) and (1.18), we have k—l k—l n 2k2s zip. s (1+o(1>>2(,) _. .921 s 321 TI. lC-l 23 n = (1 + 0(1))Zns(1 _k,._li:)2(n—k) ( s21 k—l k2s+1bs n S (1 + 0(1)):=:1 (k _1)ns(1_ r—k)2(n—k)( k—I CSMZ : (1 170(1))ng _1 S (1+ o(I))max{cs I I S s S k —1}u2. 2 k) (1 __ T—k)2(n—k) 2 k) (1 _ ,r—k)2(n—k) (1.17) (1.18) (1.19) (1.20) Next, we will show c, ——> 0 for 1 S s S k — 1. To do this, we estimate In cs. Substitute (1.17) for b, in (1.19) and next take the In of the both sides of (1.19). 24 Then we have 1110. = —slnn + (n — 2k + s)ln(l — r-2k(27~k _ ,3» —2(n—k)ln(l—r"“)+(2s+1)lnk. (1.21) Expand two In terms containing r in (1.21) and rearrange it. Here we need to recall k 2 Ik*] + 2. Then (1.21) becomes In cs 2 —s Inn + nr‘2k+s + 0(3 ln k) [I —s Inn + nr‘sz + 0(3 log log n) (1.22) Subcase I: Let s 2 o(log n) Using k 2 Ik*] + 2 Z k*, we have _ ‘ rsnr 2k ,. (10s 70“ n(log e)2 ,r—2k-I-s l/\ n log n)4 clogn ( n(log e)2’ |/\ where0_ k’“ 2 logn — (2loglogn — logloge) and hence k Zlogn—min{t—1,2loglogn—logloge}. (1.25) N ow we evaluate a new term which will be used later: _ _ 2 __ .___ n27, 2k tzrlogn 7. 2]. t = r2<1°8“-k>-1. (1.26) From (1.25), we have 2(log n — k) S 2min{t—1,2loglogn — log log e}. Hence the utmost right side of (1.26) has an upper bound T2min{t—-1,2loglogn—1081083}—t. (1.27) Ift S 210g log n — log log e + l, (1.27) has an upper bound Ift > 210g logn — log log 6 + 1, (1.27) has an upper bound 7,2(2 loglog n—log log e)—(2 log log n—log log e+1) In both cases, (1.27) has an upper bound (ln r)(log n)2. 7‘ 7'2 log log n—log log e—-1 : (1.28) 26 Combining (1.26) through (1.28), we have n2T—2k—t < (ln r)(log ”)2 _ 7" . (1.29) Substituting (1.24) for s in (1.22), we have In C, = —(-log n — t) lnn + nr-2k+(l°5”_t) + (log n — o(log n))(log log n)O(1). (1.30) Simplifying (1.30), we have In c, = ——(lnr)(log n)2 + n2r_2k—t + tlnn + O((logn)(loglogn)). (1.31) Substituting (1.29) in (1.31), we have In C, S —(ln r)(logn)2 + 1(1n r)(log n)2 r +0(log n)lnn + C((log n)(log log 71)). (1.32) Simplifying (1.32), we finally have In C, S _r;1(lnr)(logn)2 + 0((log n)2) ——> —00. Therefore, cs—>0 for 1SsSk—1 and hence k—l Z asPs S (1+ 0(1))max{cs| 1S 3 S k —1},a2 = o(pQ). 3:1 So far, we showed the following: Case 1: akPk = o(uz). Case 2: aoPo — a2 = 0(a2). Case 3: 2k”1 asPs = 0(a2). 3:1 27 Therefore, for k = [16*] + 2, we have Elel-u2 P(X =0) 3 y, 21:20 asPs _ [“2 #2 (aoPo — #2) + akPk + 2’3: M. #2 = 0(1). This implies that for any k 2 L1c*_| + 2, a random digraph has a dominating k-set almost surely. Therefore a random digraph should have domination number either |_1c*j + 1 or [19*] + 2. This completes the proof. I Remark: (1) We have shown in Theorem 1.3.2 that a —+ 0 if k = [16*] and that a ——> oo ifk = [19*] +2. What ifk = (16*) +1? We let 1c 2 (12*) +1 and for computational convenience take the probability p = 5 When n —> oo in such a way that n = 22‘ fori: 1,2,... ,we havek—k* :1—logloge > 0.4- and so ,u —> 00 as i—-> 00. When n ——> oo in such a way that n = (221+11n2_| for i = 1,2, . .. , we have k — k“ = C(fi) as i —> 00 and so ,u —> 0 as i —> 00. In Theorem 1.3.2, we analyzed the second moment under the condition that k = [W] + 2 but it is easily checked that the same result holds for k = |_1c*j +1 if )a —> 00. Therefore almost every Dn has domination number [16*] +1 (or Lk*j + 2) when p = % and n —> oo in such a way that n = 22‘ (or n = L22i+11n2‘|), respectively. This means that the result of Theorem 1.3.2 is best possible. (2) The independence domination number a’(D) of a digraph D is the minimum cardinality of all independent and dominating sets of D. Tomescu showed in [T090] that the independence domination number oz’ of every digraph in the model Dml/Z 28 satisfies log2 n — log2 log2 n — 1.43 S a’ S log2 n — log2 log2 n + 2.11 almost surely and hence 0’ takes at most four distinct consecutive values. We have shown that the domination number oz of every digraph in DWI/2 is either [_log2 n — 210g2 log2 n + log2 log2 e + 1] or [log2 n — 210g2 log2 n + log2 log2 e + 2]. Note that it is easy to see a S 01’ whenever an independent dominating set exists. The two results are consistent with the fact that oz S a’. Chapter 2 Oriented Trees 2.1 The Domination Number of an Oriented Tree In this section we study the relations among the domination number, the inde- pendent domination number, and the independence number of an oriented tree and establish their bounds. An oriented tree is a tree in which each edge is assigned a unique direction and an oriented forest is defined analogously. A kernel of a digraph D is an independent and dominating set of vertices of D and the independent domination number of D, denoted by a’ (D), is the minimum cardinality of all kernels of D. A 3—cycle has no kernel and a 4—cycle has two kernels. But J. von Neumann and O. Morgenstern showed [NeM44] that every digraph without cycles has a unique kernel, and M. Richardson showed [Ri53] that every digraph without odd cycles has a kernel. The proofs were long and involved. However, for oriented forests (and hence oriented trees), we have the following short algorithmic proof. Theorem 2.1.1 Every oriented tree T has a kernel. Proof: It is sufficient to prove this theorem for oriented forests and so we shall state an algorithm which finds a kernel for an oriented forest T. The algorithm begins 29 30 by putting vertices with indegree zero into a kernel. Next we remove the vertices that are already in the kernel together with their out—neighbors to get a new oriented forest and repeat this process for the new oriented forest. Algorithm: Let T1 = T be the given oriented forest and let K0 : a3. Put i = 1 and go to (1). (1) Choose the set S,- of all vertices with indegree zero in the oriented forest Ti and let K,- = Ki_1 U 5,. (2) Let Ti+1 be the induced oriented forest T,[V — N+[K,-]]. If T,“ is an empty digraph, let K = K, and stop. Otherwise, return to (1) putting i = i + 1. I Let T’ be an oriented tree with n vertices. Then the average indegree of T’ is (Z indeg(v))/n : n —1 <1. UET’ n Thus there is a vertex v of T’ with indegree zero. This implies that the above algorithm terminates after finitely many steps. It is obvious that K is a dominating set of T. To show that K is an independent set, we let u and v be in K. Assume there is an arc between u and i), say, an in T. Then, by (1), u and i) cannot be chosen for K in the same step. If u were chosen for K in an earlier step than the step in which i) was chosen, then 1) would not be in K. Therefore 1) must be chosen for K in an earlier step i than the step in which it is chosen for K. For this, u should have been deleted in an earlier step than the step i. Thus u is not in K, which contradicts the fact that u is in K. I We note that the complexity of this algorithm is C(n2). Theorem 2.1.2 Every oriented tree T has a unique kernel. Proof: Suppose that T has two distinct kernels K and L. Then any one of K and L cannot be a proper subset of the other. Otherwise, one of them contains an arc 31 and cannot be independent. Let v1 be a vertex in K — L. Then there is a vertex 122 in L — K that dominates v1 and next there is a vertex v3 7é v1 in K — L that dominates '02. Repeat this argument in turn. Then we have a sequence {12,-} of vertices such that v, 75 12,-”. Let j be the smallest integer such that v, = 2);, for some k < j. Then 2);, = 1),, vj_1, . . . , 2);, is a semicycle of length at least 3. This contradicts that T is an oriented tree. I Theorem 1.1.3 implies o(G) S ,6(G) for undirected graphs G. But it does not hold for directed graphs as we have already seen in a directed 3-cycle. However, for oriented trees, it still is true. Corollary 2.1.3 Let T be an oriented tree. Then we have 1S a(T) S o/(T) S E(T) S n — 1 and MT) 2 71/2- Proof: The first part is immediate from the definitions. For the second part, observe that the independence number of an oriented tree is the same as that of the underlying unoriented tree. I Here is an example that shows that the three invariants need not be equal. Let n 2 4 be an integer and let T be an oriented tree with V = {211,- - - ,un,v1,- - - ,vn} and E = {(111,113) I j = 2,---,n} U {(211,123) |j= 2,---,n} U {(u1,v1)}. Then it is easy to see that o(T) = 2, oz’(T) = n + 1, and fl(T) : 2n — 2. Therefore we have a(T) < a’(T) < MT). Let oz, 01’, fl, and n be positive integers satisfying 1 S a S oz’ S B S n — 1 and E _>_ n/ 2. Then can we construct an oriented tree T of order n having oz(T) = a, a’(T) 2 oz’, and ,8(T) = fl? By checking all oriented trees with four vertices, we know 32 that all possible outcomes of (a, a’, fl) are (1, 1, 3), (2, 2, 2), (2, 3, 3), and (3, 3, 3). Thus there are no oriented trees of order 4 having, for example, the outcome (1,2,3). Theorem 2.1.4 Let n 2 2 be an integer. Then for any oz such that 1 S oz S n — 1, there is an oriented tree T of order n whose domination number is a. Proof: We construct T as follows. The vertex set of T is V = [n] and the arcs consist of (i,n) for i = 1,2,...,a—1 and (n,j) forj = oz,a+1,...,n— 1. Then T is an oriented tree and {1, 2, . . . , a — 1, n} is a minimum dominating set of T. Therefore T has domination number a. I Theorem 2.1.5 Let n 2 2 be an integer. Then for any a’ such that 1 S a’ S n -— 1, there is an oriented tree T of order n whose independent domination number is a’. Proof: We construct T as follows. The vertex set of T is V = [n]. If 01’ Z (n— 1) / 2, then the arcs consist of (i,n) fori = 1,2, . . . , a’ and (j,j+a’) forj = 1,2, . . . ,n—a’—1. If oz’ < (n —1)/2, then the arcs consist of (i,n) for i = 1,2,...,a’, (j,j + a’) for j = 1,2, . . . ,a’, and (a,k) for k = 2a + 1,... ,n — 1. Then T is an oriented tree and {1,2, . . . , oz’} is the kernel of T. Therefore T has independence domination number 01’. I 2.2 The Domination Number of a Binary Tree In this section we study relations among the domination number, the independent domination number, and the independence number of a binary tree and establish their bounds. A binary (search) tree is an oriented tree which enjoys the following properties (see [KON73] ): 33 (1) There is a unique vertex v0 (called the root) such that for any vertex 1) distinct from 120 there is one and only one path starting at v0 and ending at v. (2) For each vertex v the number of arcs beginning with v is zero or two. In the former case v is called a leaf while in the latter case it is called an interior vertex. (3) The set of arcs is partitioned into two sets L and R (the left and right arcs, respectively). For each interior vertex there is precisely one left arc and one right arc starting with this vertex. Equivalently (see [MeM77]), a binary (search) tree may be defined as an oriented rooted tree that consists either of a single vertex or is constructed from an ordered pair of smaller binary trees by joining their roots from a new vertex that serves as the root in the tree thus formed. The vertices are not labeled, although the root is distinguished from the remaining vertices, and two such trees are regarded as the same if and only if they have the same ordered pair of branches with respect to their roots. Notice that every vertex is incident with either zero or two arcs that lead away from the root; this fact implies that such trees must have an odd number of vertices. Let T be a binary tree on 2n + 1 vertices. Then T has n interior vertices and n + 1 leaves. Let IO, 11, 12 be the sets of interior vertices with zero leaves, only one leaf, two leaves, respectively. It is of interest to observe that [Igl : |Iol + 1 since 110|+|11|+|12| = n and 111|+ 2|12| = 7. +1. Let T be a binary tree. The level number of a vertex v in T is the length of the unique path from the root to v in T and the height of T is the maximum of the level numbers of the vertices of T. A binary tree of height h is balanced if every leaf has distance h or h — 1 from the root, while it is fully balanced if every leaf has distance h from the root. Now we can state the main theorem of this section. 34 Theorem 2.2.1 Let T be a binary tree on 2n + 1 vertices. Then we have (1) 0(T) S 0/(T) S MT), (2) r2”; 11 Samm, 2(2n+1)+1 3 (3) n+1Sfl(T)SL 1- Proof: Corollary 2.1.3 implies (1). To prove (2), observe that every vertex in T dominates at most three vertices and that the set of all interior vertices of T is a dominating set for T. This establishes (2). The set of all leaves of T forms an independent set of cardinality n + 1 and hence n + 1 S 3 (T) Now we want to prove the last inequality. Let |T| be the underlying tree of the binary tree T. Suppose S = {u1,u2, - - - ,m.} is any independent set in |T|. For each i = 2, - . - , k, there is a unique ul — u,- path in |T|. Let R be the set of all predecessors of u,- in the paths for i = 2, - - -,k. Since the set R is disjoint from the set S', we have [RI S (2n + 1) — k. In addition, since every vertex in |T| has degree at most 3, we have (k —1)/2 S IRI. Therefore we have (k —1)/2 S (2n +1) — k and hence k _<_ [2(2n+1)+1]/3. . Here is an example that shows the three invariants in (1) need not be equal. Let n be an odd integer. Consider any binary tree of order 2n + 1 and height n. Such a tree always has a leaf adjacent from the root. Now attach two new vertices to this leaf. The resulting oriented tree T is a binary tree of order 2n + 3. It is easily seen that oz(T) = n +1, a’(T) = n + 2, and ,3(T) = n + 3. Now let us consider the sharpness of the bounds of (2) and (3) in Theorem 2.2.1 and let T3 denote the binary tree of order 3. The bounds in (2) are sharp. Let T be any binary tree of height n. Then the set of all interior vertices of T is a minimum dominating set for T and so a(T) : n. 35 Hence the upper bound in (2) is sharp. To see the sharpness of the lower bound of (2), there are three cases to consider. Case 1: 2n + 1 = 3k. Consider k copies of T3. Put one of these copies with the root at the bottom and stack the remaining k — 1 copies one by one from left to right by joining the leaf of the bottom copy to the roots of two stacking copies. Observe that k -— 1 is even in this case and hence this stacking is always possible. It is easy to see that the resulting binary tree has order 2n + 1 and domination number k = (2n +1)/3. Case 2: 2n + 1 = 3k + 1. Consider k copies of T3 and a single vertex. Put the single vertex at the bottom, which will serve as a root, and stack two copies by joining the root at the bottom to the roots of two stacking copies. Next stack the remaining k — 2 copies one by one from left to right by joining the leaf of the bottom to the roots of two stacking copies. Observe that k is even in this case and hence this stacking is always possible. It is easy to see that the resulting binary tree has order 2n + 1 and domination number k + 1 = [(2n + 1)/3l. Case 3: 2n+1 = 3k+2. Consider k copies of T3 and two vertices. Put one of these copies with the root at the bottom and stack the remaining k — 1 copies one by one from left to right by joining the leaf of the bottom to the roots of two stacking copies. Now join the remaining two vertices from any one of the leaves of the binary tree already constructed. Observe that k — 1 is even in this case and hence this stacking is always possible. It is easy to see that the resulting binary tree has order 2n + 1 and domination number k + 1 = [(2n + 1)/31. The lower bound in (3) is sharp. A binary tree of order 2n + 1 and height n has independence number n + 1. There is a binary tree whose independence number attains the upper bound in (3) 36 for infinitely many n. For example, a fully balanced binary tree of even height will do. 2.3 The Expected Independent Domination Num- ber of Random Binary Trees In this section we shall derive a formula for the expected value u(2n + 1) of the independent domination number of a random binary tree with 2n + 1 vertices and we shall determine the asymptotic behavior of u(2n + 1) as n goes to infinity. Let T be a binary tree. If we remove the root r of T, along with all arcs incident from r, we obtain a (possibly empty) ordered pair of disjoint binary trees, or 1- branches, whose roots were originally joined from r. Let y2n+1 denote the number of binary trees with 2n + 1 vertices. Clearly, y1 = 1 and we know that y2n+1 = Zyiyj (2.1) for n 2 1, where the sum is over all i and j such that i and j are odd and i+j = 2n. If we let y = y(:v) = Z y2n+1wzn+1 n=0 be the ordinary generating function for binary trees, then it follows from equation (2.1) that 00 2 1 y = Zy2n+1$n+ n=0 OO 2 1 = y1$ + Z y2n+1zv N n=1 = a? + 2(2 y,y,~)x2”+1 n=1 2 .3 + x :(zwxwv) 37 = :r(1+ yz) (2-2) 1 =——1—1—421/2 2. 2,1 ( a: > 1 < 3) °° (2:) = Z $2n+1, (2.4:) n=0 n + 1 where the inner sums are over all i and j such that i and j are odd and i + j = 2n. This, of course, is a well-known argument (see [Ca58] or [M083]). On the other hand, we may find the generating function y for binary trees using slightly different approach. Let T be a binary tree with order at least 3 and root r and let T3 denote the binary subtree of T with 3 vertices and the same root r. If we remove T3 of T, along with all arcs incident with vertices in T3, we obtain an ordered 4-tuple (B1, 82, B3, B4) of disjoint binary trees, or 2-branches, satisfying the following three conditions: (i) Both B1 and B2 are either empty binary trees or both non-empty binary trees. (ii) Both B3 and B4 are either empty binary trees or both non-empty binary trees. (iii) The roots of B1 and B2 were originally joined from the left leaf of T3 and the roots of B3 and B4 from the right leaf of T3. Now, using the same technique used to derive equation (2.2), we have y = a: + x3(1+ 23,2 + 31“) (2-5) which is equivalent to y = :c(1 + y2). Lemma 2.3.1 Let T be a binary tree. Then the independent domination number of T is one more than the sum of the independent domination numbers of all 2-branches ofT. Proof: This follows immediately from the algorithm in Theorem 2.1.1. I 38 For 1 S k S 2n + 1, let y2n+1,;.c denote the number of binary trees of order 2n + 1 whose independent domination number is exactly k. Let Y = Y(w, z) 2 £8331 y2n+1‘kzk):z:2”+1. n=0 k=1 It follows by a slight extension of the argument used to establish equation (2.5) that Y = 23: + 2x3(1+ 2Y2 + Y4). (2.6) The factor 2 is present in equation (2.6) because of Lemma 2.3.1. Here we note that y = Y($,1). Theorem 2.3.2 Let n(2n +1) denote the expected value of the independent domina- tion numbers of the y2n+1 binary trees with 2n + 1 vertices and define M : M($) : Z [1(21’1, +1)y2n+1$2n+1. 71:0 Then we have y M = —. 2.7 1— 4:;r2y2 ( ) Proof: It is easy to see that M : M($) : : n(2n +1)y2n+1:r2"+1 = Yz(:c,1). 71:0 If we differentiate both sides of equation (2.6) with respect to 2, set 2 = 1, appeal to the fact that equations (2.2) and (2.5) are equivalent, and solve for Yz(:c,1), we find the required result. I Of course M (m) is the ordinary generating function for the total sum of the inde- pendent domination numbers of binary trees. Therefore, using Maclaurin expansion of M(:r), we could find directly the expected value ,u(2n + 1) of the independent domination numbers of binary trees for small n. Actually, using (2.3), we have 2x MW 2 \/1— 4$2(1+ \/1— 4x2)(2 - \/1— 4352), (2.8) 39 and routine use of Mathematica produces Mm = x + x3 + 6:135 +1717 + 6629 + 234.211 + 876213 +3265a:15 + 123301?” + 467663019 + - - - . Here is a table for ,u(2n + 1) and u(2n +1)/(2n +1). The entries for 2n +1 S 9 were verified by drawing all of the diagrams for binary trees with up to 9 vertices. Table 2.1: Values of ,u(2n +1) and u(2n +1)/(2n +1) 2n+1 +1 Furthermore, we can derive a reasonably explicit formula for ,u(2n + 1) as follows. Corollary 2.3.3 The expected value of the independent domination numbers of bi- nary trees of order 2n + 1 is < n >k 2 1 = k 1 2k—, 2.9 u Z<+> <27». H where the sum is over all even integers k such that 0 S k S n. Proof: The following identity appears in [Wi90]: (1;__ ”1‘41: " — :0: Mm,“ (210) 2r ) k=0 kl(k+n)l 40 for integer n 2 1. Using (2.3) and (2.10), we have y(2my)n :: Znyn+1$n 1—\/1—43:2 )n+1$n : 2" ( 2:1: = 2n(1_ V 1 — 432 )n+l$2n+1 2:1:2 2211((i(n+1)('2k+n)$2k)$2n+1 k___0 kl(lk+n+1) °° 2k+1—n 33%“ = 12" —. 2.11 ("J”) E( k+1 )2k+1—n ( ) Hencewehave _ 31 MM _ 1—4zc2y2 = L‘s/(2%)“ 1n:0 °° °° 2k+1—2m 12k“ = 2 122m , . 2.12 E(er) k§m( k+1 )2k+1-—2m ( ) Therefore, by equating the coefficients of 51.3"“ in both sides of (2.12), we have (2”) (*2. k) k n “antllmf 21“” m and hence < 2n >k n(2n +1) = 2(k +1) where the sums are over all even integers k such that 0 S k S n. I We have seen that M (:r) is the ordinary generating function for the total sum of the independent domination numbers of binary trees. On the other hand, it is easily seen from the algorithm in Theorem 2.1.1 that M (:13) counts the number of vertices at 41 even levels of binary trees. We now want to find the ordinary generating function for the numbers of vertices at odd levels of binary trees. For 0 S k S 2n + 1, let w2n+1,k denote the number of binary trees of order 2n + 1 in which the number of vertices at odd levels is exactly k. Let oo 2n+1 W : W(:I:, z) = Z( Z w2n+1,kzk):z:2"+1. n:0 k:0 By the same argument used to establish equation (2.6), we have W = x + 223:3(1+ 2W2 + W4). (2.13) Here we note that y = W(:c,1). Theorem 2.3.4 Let A(2n + 1) denote the expected number of vertices at odd levels of the y2n+1 binary trees with 2n + 1 vertices and define 00 N : N(.’II) = Z: A(2n + I)y2n+1.’l}2n+1. n:0 Then we have N(:z:) — 2W2 (214) _ 1 — 41:23)? ' Proof: It is easy to see that N = N(;I:) = Z A(2n +1)y2n+1:r2"+1 = Wz(:v,1). n:0 If we differentiate both sides of equation (2.13) with respect to 2, set 2 = 1, appeal to the equations (2.2) and (2.5), and solve for Wz(:c, 1), we find the required result. I From (2.9) and the fact that u(2n + 1) + A(2n + 1) = 2n + 1, we have a formula for A(2n +1): A(2n+1):(2n+1)—Z(k+1) <2n >1.’ (2.15) where the sum is over all even integers k such that 0 S k S n. We also have a useful alternate formula for )1(2n + 1). 42 Corollary 2.3.5 The expected value of the number of vertices at odd levels of binary trees of order 2n + 1 is k 2.16 < 2n >k ( ) A(2n +1) = :(k +1)2k for all n 2 1, where the sum is over all odd integers k such that 0 S k S n. We, of course, have /\(1) = 0. Proof: We apply to (2.14) the same procedure as in Corollary 2.3.3. Then we have 2k<2n—k>n <2n>n /\(2n +1) 2 :01 +1) , (2.17) where the sum is over all odd integers k such that 0 S k S n. It is easy to check that <2n—k>n_ k <2n>n <2n>k' Therefore we have (2.16) from (2.17). I To determine the asymptotic behavior of n(2n + 1) / (2n +1), we need the following technical lemma, which is a slight modification of Theorem 2 in [Be74]. Lemma 2.3.6 Let A(u) 2 20:0 anu” and B(u) = 2210 bnu" be power series with radii of convergence p1 _>_ p2, respectively. Suppose that A(u) converges absolutely at u = p1. Suppose that bn > 0 for all n and that bn_1/bn approaches a limit b as n —+ 00. If Z3220 cnu” = A(u)B(u), then c,, N A(b)bn. Proof: It suffices to show that cn/bn ~ A(b). Notice that en 2 22:0 akb,,_1c and 2 p2. By repeated application of the triangle inequality, we have IA—;—: = (n(n—$162+ i czar—bat) 1C:I{+1 K b —k +2....(1k_ g; )l k:0 n 43 n n b”— s |A(b)-Zakb’°1+ Z lakl(|b’°|+l ka> k:0 k:K+1 n K k bn—k +Zlak(b ——)l. (2.18) 16:0 b” for any K such that 0 S K < n. As n goes to infinity, the first term of (2.18) goes to zero because A(u) converges at u 2 p2 = b. As n goes to infinity, the second term becomes the tail of a convergent series because A(u) converges absolutely at u = p2 = b and bunk/b7, ~ bk. As n goes to infinity, the third term goes to zero because bn_k/bn ~ bk. Letting K become large, we obtain the lemma. I Recall that our generating function M (:c) has alternate zero coefficients. To elim- inate these, we substitute u for 11:2 and define Md“) 2 Z ”(2” + 11y2n+1un- n=0 Now we can state the main result of this section. Corollary 2.3.7 The expected value of the independent domination numbers of bi- nary trees of order 2n + 1 is 1 ,u(2n +1) ~ 5(2n +1) and the expected value of the number of vertices at odd levels of binary trees of order 2n + 1 is /\(2n +1) ~ %(2n +1). Proof: It quickly follows from (2.8) that M...(u) becomes 2 MM) 2 ./1— 4u(1+ 1/1— 4u)(2 — W) Now we let A(u) = 2 (1+ ./1- 4u)(2 — ./1— 411)’ 44 and 1 B(u) : ———\/1___417 Note that A(u) can be rewritten as: 2 1—./1~4u 2 1 A(U) — §(————4u + 3 +411 + 3+4u 1/1 —4u), which has a power series expansion in u with radius of convergence 1 / 4. Moreover, it is not too hard to see this power series converges absolutely at u = 1/ 4 using the fact that V1 — 4u has a power series expansion in u with radius of convergence 1/4 which converges absolutely at u = 1/4 (see, for example, p.426, [Kn90]). On the other hand, we have 1 °° —1 B(u) = — — Z<—4)“( )u _0 for lu|<1/4. If we let it is easy to check that as n —> 00 and that b), > 0 for all n. Note that M..(u) : A(u)B(u). Therefore from Lemma 2.3.6 we have I (”(271 +1)y2n+1 N Alllbn = bn and hence b, _1 u<2n +1) ~ = (—4)”( 2 y2n+1 1 This completes the proof of the first part of the lemma. The second part of the lemma comes immediately from the fact that /\(2n + 1) : (2n + 1) — u(2n + 1). I 45 A. Meir and .1. Moon showed (see [MeM73] or [MeM75]) that the expected inde- pendence number z/(2n + 1) of binary trees of order 2n + 1 is V(2n +1) ~ (.585786--)(2n +1). We observed in Theorem 2.2.1 that 01’ (T) S B(T) for any binary tree T. Our result u(2n +1) ~ (.5)(2n +1) is consistent with these two facts. Chapter 3 Tournaments 3.1 The Domination Number of a Tournament In this section we will investigate domination numbers of specific digraphs, known as tournaments. A tournament is a diraph in which every pair of distinct vertices has exactly one arc. A transitive tournament is a tournament such that if no and vw are arcs then uw is also an arc. First we introduce an algorithm which finds a dominating set of a given tourna- ment. This algorithm is greedy in the sense that it selects a vertex that covers a maximum number of yet uncovered vertices in each step. Algorithm 3.1.1 Let T1 = T be the given tournament of order n and let So 2 (13. Put i =1 and go to (1). (1) Choose a vertex v,- with largest outdegree in T,- and let S,- : S,_1 U {vi}. (2) Let Ti+1 be the subtournament of T,- induced by V(T,) — N+[v,~]. (3) If T,“ is an empty tournament, then let S = S,- and stop. Otherwise, put i: i +1 and return to (1) I We note that the complexity of this algorithm is 0(n2). But we will see shortly that this estimate can be improved. 46 47 Let T be a tournament of order n. Then we know that there exists a vertex v in T with od(v) Z (n — 1)/2 since Evev od(v) = n(n — 1)/2 and hence the average outdegree over all vertices is (n— 1) / 2. In addition, every subdigraph of a tournament induced by a subset of V(T) is also a tournament. Using these simple observations, we prove the following theorem. Theorem 3.1.2 Let T be a tournament of order n. Then Algorithm 3.1.1 terminates after at most ]_lg(n + 1)] steps and S is a dominating set for T. Therefore we have 1 s cm s 11801 +1)1. Here, lg denotes the logarithm with base 2. Proof: Step 1: Let T1 = T and choose a vertex v1 of T1 having maximum outdegree. Step 2: Let T2 be the subtournament of T1 induced by V(Tl) — N}; [121]. Since n—l n+1 INilvlllZT+1: 2 ’ we have + n—1 n2 ;: IV(T2)] = 71 _ INT] [”1“ S 2 ' Choose a vertex 122 of T2 having maximum outdegree. Step 3: Let T3 be the subtournament of T2 induced by V(Tg) — N£[v2]. Since n +1 wanna—2, . wehave n —1 — 1+2 n3 :2 IV(T3)| = n; — |N£[v2]l S L2— S %2 Choose a vertex v3 of T3 having maximum outdegree. We continue this process up to step k. 48 Step k: Let Tk be the subtournament of Tk_1 induced by V(Tk_1) — [Vi—1 [vk_1]. Then me 1: IV(Tk)| = 711—1 — |1V'1,._1 [Wk—Ill ’nk_1 — I. _ 2 n_(20+21+.._+2k—2) — 211—1 ' Choose a vertex v), of Tk having maximum outdegree. After step k, the number of vertices in T that are not yet covered by {121, v2, . . . , vk} nk—I 2 |/\ n), — lNilvkll < n_(20+21+_..+2k—1) _ 21c . (3.1) We want to find the minimum value k’ of k that makes (3.1) zero. It is easy to see that k’ S lg(n + 1). Clearly, {v1,v2,...,vk1} is a dominating set of T. I Now we can see from Theorem 3.1.2 that the complexity of Algorithm 3.1.1 is O(n log n). We will discuss the sharpness of the upper bound in the above theorem later. The lower bound is sharp. Any transitive tournament will do. J. Moon stated in [M068] that ngn — 21g lg n] S 01(T) S [lg(n + 1)] if n 2 2, a result which was attributed to L. Moser. But this lower bound is incorrect as we have already shown. It is easily seen that every tournament is unilateral and that every strong tourna- ment has at least three vertices. 49 Corollary 3.1.3 Let T be a strong tournament of order n. Then we have 2 S a(T) S [lg(n + 1)]. Moreover, the lower bound is sharp. Proof: We know that a tournament is strong if and only if there exists a spanning cycle of the tournament. Therefore any strong tournament has no vertices of outde— gree n — 1 and so a(T) Z 2. For the sharpness, we construct T as follows. Take an n-cycle Cu and let v be a fixed vertex of C7,. Join v to all possible vertices of Cu and choose the other arcs arbitrarily. Then the resulting tournament T is strong since it has a spanning cycle and a(T) = 2. I A tournament T is called reducible if it is possible to partition its vertex set V(T) into two nonempty sets V1 and V2 in such a way that every vertex in V1 dominates all the vertices in V2. Of course, a tournament is irreducible if it is not reducible. It is well-known that a tournament T is irreducible if and only if it is strong and that a tornament of order n is reducible if and only if 21:1 od(v)) = (’2") for some k < n. Now we need the following definition. Definition 3.1.4 A minimum subtournament, denoted m(T), of a reducible tourna- ment T is the subtournament T[V1] induced by V1 satisfying the following properties: (1) V(T) is partitioned into two nonempty sets V1 and V2 in such a way that every vertex in V1 dominates all the vertices in V2. (2) V1 has the minimum cardinality for which property (1) holds. This definition says that only the arcs in T[V1] play an important role in the sense of domination. Therefore we have the following theorem. 50 Theorem 3.1.5 Let T be a reducible tournament with a minimum subtournament m(T). Then we have a(T) : a(m(T)). Proof: Let V1 2 V(m(T)) and V2 2 V(T) — V1. Then V1 and V2 are nonempty sets of vertices such that each vertex of V1 dominates all vertices in V2. Let S be a minimum dominating set of m(T) Then S is clearly a dominating set of T and hence 0(T) S 01(m(T))- Let R be a minimum dominating set of T. Then R cannot be a subset of V2 and hence R intersects V1. Therefore R 0 V1 is a dominating set of T and so R is a subset of V1. Moreover, R is a dominating set of m(T). Thus a(m(T)) S n(T). I 3.2 The Domination Number of a Random Tour- nament and the Paley Tournament Let us consider the probability space 7;, consisting of random tournaments on the vertex set V = {1,2, . . . ,n}. By a random tournament we mean here a tournament on V obtained by choosing, for each 1 S i < j S n, independently, either the arc i ] or the arc ji, where each of these two choices is equally likely. Observe that all the 2(3) possible tournaments on V are equally likely. Theorem 3.2.1 A random tournament T E 7;, has domination number either |_k,,.] +1 or ]_k,.] + 2, where k... = lgn—2lglgn+lglge and lg denotes the logarithm with base 2. 51 Proof: For each T E Tn, let X(T) be the number of dominating k-sets of T. If K is a fixed k-set of vertices, then P(K dominates a fixed vertex in V — K) = 1 — 2"“ and P(K dominates all vertices in V — K) = (1 — 2"“)""°. Therefore, we have E[X] = (Z)(1— 2*)“. The rest of this proof is exactly the same as the proof of Theorem 1.3.2 once we take r=2.I Now let us consider the sharpness of the upper bound of theorem 3.1.2. Theorem 3.2.1 says that not only do tournaments of order n with a = (1 + 0(1)) lg n exist, but when n is large, the overwhelming majority of tournaments will have a domination number near lg n. Can we construct such a tournament? The proof of Theorem 3.1.2 strongly suggests that a quasi-random tournament has a large domination number (see [ChG91]). Then do quasi-random tournaments really have domination number very close to the upper bound [lg(n + 1)] for n sufficiently large? A well—known example of a quasi-random tournament is the so—called Paley tournament Qp(Zp,E). For a prime p E 3 (mod 4), the vertices of (2,, consist of integers modulo p. A pair (i,j) E E iff i —j is a non—zero quadratic residue modulo p, i.e., iff (1%) = 1, where we use the familiar Legendre symbol. Then (2,, is a well- defined (p— 1) / 2—regular quasi—random tournament (see [ChG91]). It is easily checked that a(Qp) = |_lg(p +1)] for p = 3,7,11, and 19. But a(Q31) S 4 < (lg(31+1)] since {1,2,4,5,7,8,9,10,14,16,18,l9,20,25,28} is the set of all non—zero quadratic residues modulo 31 and hence {0, 27, 29,31} is a dominating set for Q31. This shows that a(Qp) = [lg(p + 1)] does not hold for some p. What if p is large enough? Now 52 we consider Schiitte property. We say that a tournament has (Schiitte) property 5;, if for every set of k vertices there is one vertex that dominates them all. For example, a directed 3-cycle has property 51. The following lemma is in [GrS71], but it was used to find a lower bound of p for Q], to have property Sk. Lemma 3.2.2 ([GrS71]) Ifk satisfies the inequality 1) — {(k — 2)2k-1 +1}\/p7 — 2“—1 > 0, then the Paley tournament 6),, has property 5),. Proof: It is easily seen that 62,, has property 5;. if and only if for all a1, . . . ,an E V there exists an x E V such that x—a, ( )=1 for 1SiSk. Set x(a) = (g) and let A = {(11, . . . ,ak} denote a set of k arbitrary fixed vertices of Qp. Define k f(A) = Z H{1+X(IB -aj)}- xEV—A j=1 Then f (A)2~llc counts the number of vertices that dominate all the vertices in A. Now define p—l k 9(A) = 2 H{1 + X(‘13 - (11)}. x=0j=1 MA) = Z Hf1+ x(a. — (11)}- i:0 j::1 Then we have f(A) = g(A) — h(A). Expanding the inner terms of g(A), we have p—l k p—l p—l k 9(A)=21+ZZX($—01)+ZZ Z X(w—aj1)"'X($—aj.)- 21:0 112:0 j=1 1720 3:2 j1<"'<.ls 53 The first two terms of this are p and 0, respectively. To estimate the remaining terms we use the result of Burgess (Bu62]: 1:111 — a..)~-x 0. I Now we are ready to state the following theorem. 54 Theorem 3.2.3 The domination number of the Paley tournament 6),, satisfies an.) > (1+ 0(1))1181». 2 Proof: Suppose Qp satisfies property Sk. Then for every set S of k vertices there exists a vertex not in S that is dominated by S and hence every dominating set must have more than k vertices. Consequently, 01(Qp) > k if Qp satisfies property Sk. Now we know that (2,, satisfies S), if {(k — 2)2k-1 + 1),/1.7+ 2k-1 < p (3.2) and hence we want to find the maximum value k’ of k satisfying (3.2) when p is large. But it is easy to check k’ < lg(p + 1) and so we let k=clgp—dlglgP+1, c>0andd20. Then the left side of (3.2) becomes pc—l/Z pc i pc—l “(lgpr 1320112)” + up + (18p)d}' (3'3) To make the second factor of (3.3) smaller than 1 when p —) 00, we must have c S 1/2. But the maximum value k’ of k can be obtained when c = 1 / 2 and d > 0. Therefore , 1 k = Elgp—dlglgp+ 1, d> 0 and so an.) > k'= (1+ 0(1)); 1817- - Open Problems This thesis covers only a portion of the topic of domination for graphs and digraphs. But we believe that many more results will be forthcoming in the near future. In the course of our researches, we struggled with many difficult questions. Among them, we would like to state the following unsolved problems. (1) We have shown that a digraph D with order n and minimum indegree 6‘ Z 1 has domination number MD) 3 L26- +1 n1 in Theorem 1.2.6 and that this upper bound is sharp for infinitely many n when 5” = 1 in Theorem 1.2.9. For 6‘ = 2, can we either sharpen this upper bound or construct a digraph with order n and 6— = 2 whose domination number is (266:1; n] ? (2) Regarding binary trees as undirected graphs, A. Meir and J. Moon showed in [MeM77] that the expected domination number of a random binary tree with 2n + 1 vertices is asymptotic to (.3782---)(2n + 1). What about the asymptotics of the expected domination number of a random binary tree in our sense, that is, if we regard binary trees as directed away from the root? The details will be published elsewhere. (3) What is the asymptotic behabior of the expected domination number and the expected independent domination number of a random oriented tree? This seems to be a difficult problem even for the simplest families of oriented trees, such as 55 56 orientations of the paths of order n. (4) We have shown that a tournament T of order n has domination number (X(T) S [lg(n +1)l in Theorem 3.1.2. Here lg denotes the logarithm with base 2. Can we either sharpen this upper bound or construct a tournament with n vertices whose domination number is this upper bound? (5) Can we find the domination number of the Paley tournament 6),, as a function of p? What about the asymptotics for the domination number of Qp? (6) Finally, we want to state a conjecture, which is not unrelated to the main topic of this thesis. Conjecture: Let C be a connected cubic (or 3-regular) graph with n vertices. Then a(G) : 1333). The author encountered the same conjecture in [Re9x] but our conjecture was established independently due to the following clues. First, it is true for connected cubic graphs with order up to 14. We checked 621 diagrams in [ReW9x] for unlabeled connected cubic graphs with up to 14 vertices. Second, Robinson and Wormald showed in [ROW92] that almost all cubic graphs are hamiltonian. Since we know that a cycle of order n has domination number [n/3], it follows that almost all cubic graphs satisfy the conjecture. In addition, this conjecture is best possible. To see this, consider a cubic graph G with 6n vertices consisting of the cycle 'Ul’Ug - --v6nv1 and the edges Ufii+106i+4, v6i+2vsi+5, and v6i+3vsi+6 for i = 0,. . . , n — 1. Since G contains a Hamiltonian cycle, a(G) S [6n/3] = 2n. On the other hand, any dominating set of C must contain at I. 57 least two of the six vertices U614.“ - - - ,v6,+6 for each i and hence a(G) 2 2n. Therefore a(G) = 2n = [6n/3]. We note that the conjecture requires that all vertices of G should have degree exactly three rather than at least three. To see this, we consider a cubic graph H with 8 vertices consisting of the cycle vovl - - - mm and the edges mm, mm, v2v5, and v3v6. Next construct a graph G from 3n disjoint copies of H by adding an edge between all pairs of vertices both of which are labeled v0. Then it is easily checked that oz(G) = 9n > 8n = HVl/3]. Bibliography [AlS92] N. Alon and J. H. Spencer, The Probabibistic Method, Wiley, New York [B674] E. A. Bender, Asymptotic Method in Enumeration, SIAM Review 16 (1974), 485-515. [Be58] C. Berge, Theory of Graphs and its Applications, Dunrod, Paris 1958. [B085] B. Bollobas, Random Graphs, Academic, London 1985. [Bu62] D. A. Burgess, On character sum and primitive roots, Proc. London Math. Soc. 12 (1962), 179-192. [C2158] A. Caley, On the analytical forms called trees, Philos. Mag. 28 (1858), 374-378. [Collected Mathematical Papers, Cambridge 4 (1891), 112—115.] [ChG91] F. R. K. Chung and R. L. Graham, Quasi-random tournaments, J. of Graph Theory 15 (1991), 173—198. [COH77] E. J. Cockayne and S. T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), 247-261. [GrS71] R. L. Graham and J. H. Spencer, A constructive solution to a tournament problem, Canad. Math. Bull. 14 (1971), 45-48. [HaNoC65] F. Harary, R. Z. Norman, and D. Cartwright, Structural Models, Wiley, New York 1965. [HeL90(a)] S. T. Hedetniemi and R. C. Laskar, Introduction, Discrete Math. 86 (1990), 3—9. [HeL90(b)] S. T. Hedetniemi and R. C. Laskar, Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete Math. 86 (1990), 257-277. [Kn90] K. Knopp, Theory and Application of Infinite Series, Dover, Mineola, 1990. [KON73] A. G. Konheim and D. J. Newman, A note on growing binary trees, J. of Graph Theory 4 (1973), 57-63. [K036] D. K0nig, Theory of Finite and Infinite Graphs, Birkhauser, Boston 1990. 58 59 [L075] L. Lovasz, On the ratio of optimal integral and fractional covers, Discrete Math. 13 (1975), 383-390. [MeM73] A. Meir and J. W. Moon, The Expected Node-Independence Number of Random Trees, Proc. Kon. Ned. Akad. v. Wetensch 76 (1973), 335-341. [MeM75] A. Meir and J. W. Moon, The Expected Node—Independence Number of Various Types of Trees, Recent Advances in Graph Theory, Praha (1975), 351-363. [MeM77] A. Meir and J. W. Moon, Packing and covering constants for certain families of trees. I, J. of Graph Theory 1 (1977), 157-174. [Mc889] W. McCuaig and B. Shepherd, Domination in graphs with minimum de- gree two, J. of Graph Theory 13 (1989), 749-762. [M068] J. W. Moon, Topics on Tournament, Holt, Rinehart & Winston, New York 1968. [M083] J. W. Moon, On level numbers of t-ary trees, SIAM J. Alg. Disc. Math. 4 (1983), 8-13. [NeM44] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, Princeton Univ. Press, Princeton 1944. [Or62] O. Ore, Theory of Graphs, Amer. Math. Soc. Collq. Publ. 38, Amer. Math. Soc., Providence 1962. [Pa85] E.M. Palmer, Graphical Evolution, Wiley, New York 1985. [ReW9x] R. C. Read and R. J. Wilson, Atlas of Graph Theory, Oxford Univ. Press (to appear). [Re9x] B. Reed, Paths, stars, and the number three, preprint. [Ri53] M. Richardson, Solutions of irreflexive relations, Ann. Math. 58 (1953), 573—590. [R0W92] R. W. Robinson and N. C. Wormald, Almost all cubic graphs are hamil— tonian, Random Struct. Alg. 3 (1992), 117-125. [T090] I. Tomescu, Almost all digraphs have a kernel, Random Graphs, vol 2 (M. Karoriski, J. Jaworski, and A. Ruciriski, ed.), Wiley, Chichester, 1990, 325-340. [We81] K. Weber, Domination number for almost every graph, Rostock. Math. Kolloq. 16 (1981), 31-43. [Wi90] H. S. Wilf, generatingfuctionology, Academic, San Diego 1990. 1 LIBRQRIES [I] 1| 1|] 31293013L®1527 HICHIGQN STQTE UNIV ..............2............ ......... . ...... if...» ..2..... _ . . . . . . .... .... .51....2... . . . ....f .....1. . ......... . ...t. , . 1.172172...) ......._.. . . . . 23.2.: <..)1......, ............ .52..