The Inverse Domination Number Problem, DI-Pathological Graphs, and Fractional Analogues by David Prier A dissertation submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama May 14, 2010 Keywords: graph theory, domination, inverse domination, fractional dominating functions Copyright 2010 by David Prier Approved by Peter D. Johnson, Chair, Professor of Mathematics and Statistics Dean Ho man, Professor of Mathematics and Statistics Chris Rodger, Scharnagel Professor of Mathematics and Statistics Abstract The conjecture that (G) 0(G) is unproven where (G) is the vertex independence number and 0(G) is the inverse domination number of a simple graph G. We have found the conjecture to be true for all graphs with domination number less than 5 and for many other in nite classes of graphs. We examine related questions involving DI-pathological graphs which are graphs such that every maximal independent set intersects with every minimum dominating set. Finally, we use two central results in linear programming to characterize minimum fractional total dominating functions as well as maximum fractional open neighborhood packings for certain graphs. ii Acknowledgments I would like to thank the following people in no particular order. My parents, Mike and Rosie Prier, for their encouragement and support especially in matters of education. My fellow Auburn graduate students who provided me with a welcoming and nourishing environment for the past four years. My advisor, Pete Johnson, for his constant guidance and direction. The professors of Auburn?s Department of Mathematics and Statistics, especially Chris Rodger who welcomed me to Auburn and Michel Smith who has been a great support. My siblings, aunts, uncles, grandparents, cousins, and other family members who have always been a rock on which I can rely. Any nally, I want to thank my wife Maria who continues to give me more love and support than I?ll ever deserve. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Basic De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 The Inverse Domination Number . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 (G) 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 3 (G) 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 DI-Pathological Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1 Minimal DI-Pathological Graphs with Domination Number Three . . . . . . 18 3.2 DI-Pathological Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4 The Principle of Strong Duality and the Principle of Complementary Slackness . 34 4.1 The Fractional Domination Number and the Fractional Closed Neighborhood Packing Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2 The Fractional Total Domination Number and the Fractional Open Neighbor- hood Packing Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.3 The Fractional Independence Number, the Fractional Clique-Independence Number, and their Dual Linear Programs . . . . . . . . . . . . . . . . . . . . 39 4.4 The Principle of Complementary Slackness . . . . . . . . . . . . . . . . . . . 40 5 Total Domination Null and Open Neighborhood Packing Null Vertices . . . . . 43 iv 5.1 Fractional Total Domination . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.3 Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 v List of Figures 1.1 H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 G with the weightings assigned by f1 . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 G with the weightings assigned by f2 . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 G with the weightings assigned by f3 . . . . . . . . . . . . . . . . . . . . . . . . 5 1.6 G with the weightings assigned by g1 and g2 . . . . . . . . . . . . . . . . . . . . 6 1.7 C5 with the weightings assigned by h1 and h2 . . . . . . . . . . . . . . . . . . . 7 3.1 G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2 H minus 4 edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4 A non-DI-pathological graph G with an exploded tail of order 11 . . . . . . . . 32 3.5 A non-DI-pathological graph H with an exploded ear of order 13 . . . . . . . . 33 4.1 G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2 f1, a fractional dominating functions and h, a fractional closed neighborhood packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 vi 4.3 g, a fractional total dominating function and a fractional open neighborhood packing for C5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.4 a fractional independent function and a fractional edge covering for G . . . 40 4.5 ^ a fractional clique-independent function and ^ a fractional clique covering for G 41 5.1 n 0(mod 4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.2 i 1(mod 4), a;b 0, a+b = n 14 . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.3 i 3(mod 4), a;b 0, a+b = n 54 . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.4 i 3(mod 4), a;b 0, a+b = n 64 . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.5 a = n 24 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.6 i 0(mod 4), a;b 0, a+b = n 74 . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.7 i 0(mod 4), a;b 0, a+b = n 34 . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.8 i = n and a = n 34 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 vii Chapter 1 Introduction 1.1 Basic De nitions Throughout this dissertation, the graph G = (V;E) will be a nite simple graph with vertex set V = V(G) and edge set E = E(G). If v 2V, then the open neighborhood of v, denoted NG(v), is fu2V : uv 2Eg and the closed neighborhood of v, denoted NG[v], is fvg[NG(v). If G is the only graph in the discussion, N will replace NG. If S V, N(S) = Sv2SN(v) and N[S] = S[N(S). Let G and H be two graphs with V(G)\V(H) =;. Then G+H is the graph such that V(G + H) = V(G)[V(H) and E(G + H) = E(G)[E(H). G_H is the graph such that V(G_H) = V(G)[V(H) and E(G_H) = E(G)[E(H)[fvu : v2V(G) and u2V(H)g. A set S V is dominating (in G) if V = N[S]. The domination number of G is (G)= min[jSj: S V is dominating]. A minimum dominating set in G is a dominating set S V such that jSj = (G). A minimal dominating set is a dominating set no proper subset of which is a dominating set. A set of vertices which is dominating and disjoint from a minimum dominating set is an inverse dominating set. When G has no isolated vertices, the inverse domination number of G is 0(G) = min[jBj: B V nS for some minimum dominating set S V, and B is dominating in G]. 0(G) is well de ned when G has no isolated vertices by Theorem 1.1, below. Clearly (G) 0(G). To see an example of an inverse dominating set, consider the graph H in Figure 1.1 where (H) = 1, andfygis the unique minimum dominating set. Thus any inverse dominating set cannot include y. Therefore fx;zg is a minimum inverse dominating set and 0(H) = 2. 1 w x yz Figure 1.1: H Theorem 1.1 ([9];[10]) If G has no isolated vertices and S is a minimal dominating set in G, then V nS is dominating in G. Proof Suppose otherwise. Then there exists v 2 V(G) such that N[v]\(V nS) = ;. Therefore N[v] S. But that is a contradiction to the minimality of S since Snv would then also be a dominating set in G. For a graph G, the closed neighborhood packing number, (G), is the maximum number of disjoint closed neighborhoods in G. The open neighborhood packing number, 0(G), is the maximum number of disjoint open neighborhoods in G. As we will see in Chapter 4, (G) and 0(G) are very closely related to (G) and t(G) respectively. A set I V is independent if no two vertices of I are adjacent in G. A maximal independent set is one not properly contained in any other independent set. Clearly a max- imal independent set in G is dominating in G. The (upper) independence number (G) and the lower independence number {(G) are de ned by (G) = max[jIj: I V is inde- pendent] and {(G) = min[jIj: I V is maximal independent]. By remarks above, clearly (G) {(G) (G). Many of the above de nitions can be adapted to give analogues pertinent to the study of fractional graph theory. A fractional dominating function onGis a functionf : V(G)![0;1] such that for every v2V(G), Pu2N[v]f(u) 1. The fractional domination number of G is then f(G) = min[Pv2V(G)f(v) : f is a fractional dominating function on G]. Since the characteristic function of a dominating set is a fractional dominating function, f(G) (G). 2 v z w xy Figure 1.2: G To see an example of a fractional dominating function., consider the graph G in Figure 1.2. Here one of the minimum dominating sets is D :=fv;xg, so the characteristic function on D, f0 : V(G) ! [0;1] such that f0(v) = f0(x) = 1 and f0(w) = f0(y) = f0(z) = 0, is a fractional dominating function. However f1 : V(G) ! [0;1] such that f1(v) = 0, f1(z) = f1(w) = 12, and f1(y) = f1(x) = 14 is also a fractional dominating function, and it can be shown that it is minimum. Proving that f1 is minimum will come from arguments made later in Chapter 4. Therefore (G) = 2 while f(G) = Pu2V(G)f1(u) = 32. v z w xy 0 12 14 14 12 Figure 1.3: G with the weightings assigned by f1 An inverse fractional dominating function of G is a fractional dominating function g of G that satis es g(v) 1 f(v) for all v2V(G), for some minimum fractional dominating function f of G. From [8], if G has no isolated vertices and f is a minimum fractional dominating function of G, then 1 f is a dominating function on G. Therefore such a function g exists on graph G with no isolated vertices. The inverse fractional domination number of G is ( f)0(G) = ming[Pv2V(G)g(v)] where the minimum is taken over all inverse fractional dominating functions. Since every inverse fractional dominating function of G is a fractional dominating function of G, f(G) ( f)0(G). 3 To see an example of an inverse fractional dominating function, again consider the graph G in Figure 1.2. As mentioned above, f1 is a minimum fractional dominating func- tion. Therefore an inverse fractional dominating function, f2 : V(G)![0;1], could be any fractional dominating function such that f2(z);f2(w) 12, and f2(y);f2(x) 34. Therefore f2(z) = f2(w) = f2(x) = 12 and f2(y) = f2(v) = 0 is such an inverse fractional dominating function, and in fact since Pu2V(G)f2(u) = 32 and f(G) ( f)0(G), ( f)0(G) = 32. It can also be seen that ( f)0(G) = 32 due to the fact that f1 1 f1. This demonstrates the obvious fact that if there exists a minimum fractional dominating function g on a graph G such that g(v) 12 8v2V(G), then ( f)0(G) = f(G). v z w xy 0 12 12 120 Figure 1.4: G with the weightings assigned by f2 For another fractional analogue of the inverse dominating number, rst let D be a minimum dominating set of a graph G. A fractional inverse dominating function g of G (with respect to D) is a fractional dominating function of G such that g(v) = 0 for all v2D. In other words, g the characteristic function of V(G)nD. The fractional inverse domination number of G is ( 0)f(G) = ming[Pv2V(G)g(v)] where the minimum is taken over all fractional inverse dominating functions g (with respect to minimum dominating sets D). Because the characteristic function of a dominating set of vertices that is in the complement of a minimum dominating set is also a fractional inverse dominating function, ( 0)f(G) 0(G). To see an example of a fractional inverse dominating function, again consider graph G in Figure 1.2. As before, D =fv;xgis a minimum dominating set for G, and f0 : V(G)![0;1] such that f0(v) = f0(x) = 1 and f0(w) = f0(y) = f0(z) = 0 is the characteristic function 4 on D. Therefore a fractional inverse dominating function, f3 : V(G) ! [0;1], could be any fractional dominating function satisfying f3(v) = f3(x) = 0. Thus f3 such that f3(w) = f3(y) = f3(z) = 12, and f3(v) = f3(x) = 0 is a fractional inverse dominating function. Since P u2V(G)f3(u) = 3 2 and f(G) ( 0)f(G), ( 0)f(G) = 3 2. v z w xy 0 12 12 12 0 Figure 1.5: G with the weightings assigned by f3 A function : V(G) ! [0;1] is fractional independent if for any pair v;w of adjacent vertices of G, (v) + (w) 1; i.e., is a fractional packing of the "hypergraph" G. The fractional independence number is f(G) = max [Pu2V(G) (u)] where the maximum is taken over all fractional independent functions on G. A fractional clique-independent function of G is a function ^ : V(G)![0;1] such that for all cliques K of G, Pv2V(K) ^ (v) 1. The fractional clique-independence number of G is ^ f(G) = max^ [Pv2V(G) ^ (v)] where the maximum is taken over all fractional clique- independent functions. Clearly (G) ^ f(G) f(G). To see examples of fractional independent and fractional clique-independent functions, once again consider graphGfrom Figure 1.2. Here (G) = 2. The functiong1 : V(G)![0;1] de ned such that g1(u) = 128u 2 V(G) is certainly fractional independent, and it can be shown that g1 is in fact maximum. Thus f(G) = Pu2V(G)g1(u) = 52. However, g1 is not fractional clique-independent since g1(v) + g1(w) + g1(z) > 1 and fv;w;zg form a clique of size three in G. The function g2 : V(G) ! [0;1] de ned such that g2(x) = g2(y) = 12, and g2(v) = g2(w) = g2(z) = 13. g2 is certainly clique-independent, and it can be shown that it is maximum. Thus ^ f(G) = 2. 5 v z w xy 12 12 12 v z w xy 12 1212 12 13 13 13g1 g2 Figure 1.6: G with the weightings assigned by g1 and g2 A total dominating set of G is a set of vertices, S V(G), such that for every v2V(G), there exists a u 2 S with v 2 N(u). Notice that if G has an isolated vertex, no total dominating set exists. If G has no isolates, then the total domination number of G, denoted t(G), is the smallest size of total dominating set in G. Since every total dominating set is certainly dominating, it is clear that (G) t(G). A fractional total dominating function on G is a function f : V(G) ! [0;1] such that for every v2V(G), Pu2N(v)f(u) 1. As in the non-fractional case, notice that if G has an isolated vertex, then there is no fractional total dominating function on G. If G has no isolates, then the fractional total domination number ofGis ( t)f(G) = min[Pv2V(G)f(v) : f is a fractional total dominating function onG]. Since any fractional total dominating function on G is also a fractional dominating function, f(G) ( t)f(G). To see an example of a fractional total dominating function consider the cycle on ve vertices, C5. Clearly (G) = 2, and t(G) = 3. The function h1 : V(G)![0;1] that assigns weights of 13 to every vertex is clearly fractional dominating, but it is not total fractional dominating. In fact, it can be shown that h1 is minimum and f(C5) = 53. An example of a fractional total dominating function is h2 : V(G) ! [0;1] de ned by h2(u) = 12 for all u2C5. It can be shown that h2 is minimum and ( t)f(C5) = 52. A fractional closed neighborhood packing of G is a function g : V(G)![0;1] such that for every v2V(G), Pu2N[v]g(u) 1. The fractional closed neighborhood packing number for G is then f(G) = max[Pv2V(G)g(v) : g is a fractional closed neighborhood packing of G]. A fractional open neighborhood packing of G is a function ^g : V(G)![0;1] such that for 6 13 13 13 13 13 1212 12 12 12h1 h2 Figure 1.7: C5 with the weightings assigned by h1 and h2 every v2V(G), Pu2N(v) ^g(u) 1. The fractional open neighborhood packing number for G is then 0f(G) = max[Pv2V(G) ^g(v) : ^g is a fractional open neighborhood packing of G]. As will be explained in Chapter 4, it is true that for a simple graph G with no isolated vertices, f(G) = f(G) and ( t)f(G) = 0f(G). Now suppose G is a graph with no isolated vertices. The following inequalities follow directly from the above de nitions. i) (G) {(G) (G) ^ f(G) f(G) ii) f(G) (G) 0(G) iii) f(G) ( f)0(G) iv) f(G) ( 0)f(G) 0(G) v) f(G) ( t)f(G) t(G) In [8] the following two additional inequalities were also proven. vi) ( f)0(G) f(G) vii) ( 0)f(G) f(G) These next ve inequalities are expected to be true but have not been proven. Notice that if inequality viii were proven true, then this would immediately imply that inequality ix would be true as well due to inequality iv. Inequality x is the original Kulli and Sigarkanti conjecture discussed in the next section. Inequalities xi and xii, if true, are stronger, respec- tively, than vi and vii. 7 viii) ( f)0(G) ( 0)f(G) ix) ( f)0(G) 0(G) x) 0(G) (G) xi) ( f)0(G) ^ f(G) xii) ( 0)f(G) ^ f(G) 1.2 History The study of domination is nothing new in Graph Theory. Since the 1950?s, with the growth of computer science, the study of dominating sets in graphs has expanded rapidly. There have been over one thousand papers written on domination in graphs, and most of those papers have been written in the last 35 years. One little known paper written in 1991 by Kulli and Sigarkanti [9] introduced the inverse domination number, 0(G). It was shown that 0(G) is well de ned when G has no isolated vertices, and it was asserted that when G has no isolated vertices then 0(G) (G). The attempted proof of this assertion was invalid; this was noticed, in due course, by Gayla Domke, Jean Dunbar, Teresa Haynes, Steve Hedetniemi, and Lisa Markus, who transmitted the open question to those interested in domination. (The rst and third authors of [6] heard about the problem from Haynes, Hedetniemi, and Markus in 2000 or 2001, at a conference at Clemson University. Hedetniemi o ered a prize for a resolution of the problem: a copy of [2]. The question appeared as a conjecture in [1].) 1.3 Outline Much of Chapter 2 was inspired by the observation that if a graph G has a minimum dominating set D and a maximally independent set I which are disjoint, then 0(G) (G). Therefore a graph G such that (G) < 0(G), if such a graph exists, must be found among 8 those with no isolated vertices and the additional property that every minimum dominating set of G must have nonempty intersection with every maximally independent set of G. This class of graphs, the DI-pathological graphs, is examined in Chapter 3. In Chapter 4, two important results of linear programming are used to examine many fractional analogues to the Kulli and Sigarkanti conjecture continuing the work previously started in [8]. In Chapter 5, the tools explained in Chapter 4 are applied to minimum fractional total dominating functions, and these functions are totally characterized for certain graphs. 9 Chapter 2 The Inverse Domination Number In this chapter, we consider the inverse domination number problem originally stated in [9] which conjectures that 0(G) (G) for every simple graph with no isolated vertices. Observe that if G = K1;t then {(G) = 1 = (G) and (G) = t = 0(G); a sign that this problem may be peskier than might have been evident at rst glance. We will say that G has Property DI if there exists a minimum dominating set D V and a maximal independent (and therefore dominating) set I V nD. If such a D and I exist, then straight from the de nitions we have 0(G) jIj (G). Lemma 2.1 If G has property DI then G has no isolated vertices. Proof Suppose G did have an isolated vertex, v. Clearly, v must be in every dominating set. Therefore there cannot be two disjoint dominating sets. Therefore, a graph G such that (G) < 0(G), if there are any, will be found among graphs with no isolated vertices not having Property DI. Such graphs not having Property DI will be called DI-Pathological. We may as well look among connected graphs, because G has Property DI if and only if each component of G does, and if (G) < 0(G), then (H) < 0(H) for some component H of G. 2.1 Trees Lemma 2.2 If D V and I is maximal among the independent subsets of V nD, then I is dominating in G if and only if D N(I). 10 Proof Because I is maximal among the independent subsets of VnD, VnD N[I]. There- fore V = N[I] if and only if each vertex of D is adjacent to some vertex of I. Corollary 2.1 If G has a minimum dominating set D such that there is an independent set I V nD with D N(I), then G has Property DI. Proof Let ~I be an independent set such that I ~I V nD, maximal among all indepen- dent subsets of V nD. Then D N(I) N(~I) so ~I is a dominating independent set in the complement of D. Theorem 2.1 Every tree of order >1 has Property DI. Proof Clearly K2 has Property DI. Let T be a tree of order n 3, and let D be a minimum dominating set in T containing no leaf of T. Let u be a leaf of T. Order V(T) by the rule: v w if and only if the path in T from u to w contains v. Because T is a tree, every v2V(T)nfug has a unique immediate predecessor, i:p:(v), in this ordering. Since D contains no leafs of T, every vertex in D has at least one immediate successor, in this ordering. Now we describe an algorithm that will result in a minimum dominating set ~D in T and an independent set I V(T)n ~D such that ~D NT(I). By Corollary 2.1, this will establish that T has Property DI. We start with ~D = D and I =fug, and move out from u, processing vertices as we go, putting some in I, removing from or adding to ~D, and leaving some as they were. Obviously certain purposes must be served: ~D must continue to be a dominating set in T, j~Dj must not change, I V(T)n ~D must be independent; for this it su ces to verify that each vertex in V(T)n ~D added to I is not adjacent to any vertex already in I. Finally, arrangements must be made so that, at the end, I dominates ~D. 11 From the many ways of organizing the algorithm, choose one satisfying: when the algorithm begins the processing of w, all of the predecessors of w have been processed, and none of the successors. The satisfying of the requirements in the paragraph above can be checked as we go along; in the end, I will dominate ~D if, after each processing episode, the current I dominates ~D\ [fwg[fpredecessors of wg]. So, suppose w is an unprocessed vertex of T, w6= u, and all the predecessors of w and none of the successors of w have been processed. Let v = i:p:(w). There are 6 cases to consider. 1. If w2 ~D and v2I, do nothing and move on. [Note that if w is the support vertex adjacent to u, then w2D = ~D and u2I, so we are in case 1.] 2. If w2 ~D and v62I[ ~D, then: (a) If w has an immediate successor x2V(T)n ~D, put x in I, leave w in ~D, and move on. [Both w and x have now been processed.] (b) If all immediate successors of w are in ~D then replace ~D with ( ~Dnfwg)[fvg, put w in I, and move on. [No immediate successor of w has been processed, in this case; when each gets its turn, we will be in case 1.] Remark: if w 2 ~D then, since w has not been processed earlier, w 2 D and so, as noted above, w does have successors. 3. If w;v2 ~D then, because ~D is a minimum dominating set, w must have an immediate successor x which is not in ~D. Leave w in ~D, put x in I, and move on. [Both w and x have been processed.] 4. If w62 ~D and v2 ~D, do nothing and move on. 5. If w62 ~D and v2I, do nothing and move on. 6. If w62 ~D and v62 ~D[I, put w in I. 12 It is straightforward to see, in each case, that each new member of I is adjacent to none of the previously inducted members of I, so I remains independent. Further, at each stage, after the processing episode I dominates all members of ~D that have been processed at that point. Finally, in case 2(b), the only case in which ~D is modi ed, by exchanging w for v, it is clear that the new ~D is still dominating, and with the same number of vertices as the old ~D. Corollary 2.2 If F is a forest with no isolated vertices, then 0(F) (F). After proving Theorem 2.1 we discovered that it answers a problem posed in [3], and that the problem is also solved in [4], with a similar but more economical proof. We have given our clunkier proof because it is algorithmic, and because we think it better illuminates the following theorem. Theorem 2.2 If T is a tree of order 2, and D is a minimum dominating set in T containing at most one leaf, then there is an independent dominating set I V(T)nD. We proposed Theorem 2.2 originally as a conjecture after proving Theorem 2.1. After transmitting this problem to Michael Henning, he and two collaborators found our conjecture to be true. The proof of this will appear in [5]. It might be useful to know for which minimum dominating sets D V(T), T as above, there is an independent dominating set I V(T)nD: Theorem 2.2 asserts that any minimum dominating set for a tree containing at most one leaf is such a set. In the smallest example in which D contains 2 or more leafs of T and there is no independent dominating set I V(T)nD, T is P4, the path on 4 vertices, and D consists of the two end vertices of the path. 2.2 (G) 2 Theorem 2.3 If (G) 2 and G has no isolated vertices then G has Property DI unless G = Km;n for some m;n> 2. 13 Proof If (G) = 1, let D = fvg be any minimum dominating set. By Lemma 2.2 any independent set I maximal among independent subsets of V nD is a dominating set, so G has Property DI. Suppose that (G) = 2. Suppose that G does not have Property DI. Then for any minimum dominating set D =fx;ygin G, N(x)\N(y) =;, for if z2N(x)\N(y) VnD then fzg is an independent subset of V nD such that x;y 2 N(fzg), so G would have Property DI after all, by Corollary 2.1. Let N(x;D) = N(x)nD, N(y;D) = N(y)nD, which partition VnD, by the observation just above. Both sets are nonempty because (G) = 2 and G has no isolated vertices. By the same argument as above, appealing to Corollary 2.1, there cannot exist u 2 N(x;D) and v2N(y;D) which are not adjacent in G; that is, every vertex in N(x;D) is adjacent to every vertex in N(y;D). Therefore, if u2N(x;D) and v2N(y;D) then D0 = fu;vg is a minimum dominating set in G. Applying what has been shown about D to D0, we conclude that N(u;D0) and N(v;D0) are disjoint and that x2N(u;D0) and y2N(v;D0) are adjacent. We also conclude that N(x;D) and N(y;D) are each independent because if, for instance, some u;w2N(x;D), u6= w, are adjacent, then, taking any v 2N(y;D), we would have that w2N(u;D0)\N(v;D0), D0 =fu;vg. Thus G is a complete bipartite graph with bipartition N(x;D)[fyg, N(y;D)[fxg. Say G = Km;n, m n. Then 2 m because (G) = 2. If m = 2 then G does have Property DI; just take D to consist of the 2 vertices on one side of the bipartition and I to be the other side of the bipartition. Therefore, m;n> 2. Corollary 2.3 follows from the fact that Property DI implies 0 , and that if G = Km;n, m;n 2, then 0(G) = (G) = 2. Corollary 2.3 If (G) 2 and G has no isolated vertices then 0(G) (G). 14 Corollary 2.4 Suppose that (G) = 2 and G has no isolated vertices. Then the following are equivalent: (a) G = Km;n for some m,n > 2. (b) G does not have Property DI. (c) G does not have Property DI and for each e2E(G), G e does have Property DI. (d) G does not have Property DI and for each e2E( G), G[e does have Property DI. Proof (a) and (b) are equivalent by Theorem 2.3, and the observation that Km;n, m;n> 2, does not have Property DI. Clearly (c) or (d) implies (b). If m;n > 2 then adding or removing an edge to Km;n results in a connected graph with domination number 2 which is not Ka;b for any a;b. By Theorem 2.3, the modi ed graph must have Property DI. Thus (a) implies (c) and (d). 2.3 3 (G) 4 Lemma 2.3 Suppose that G has no isolated vertices, and that 0(G) = (G) + c for some c 1. Suppose that D is a minimum dominating set in G and I S = V nD is an independent set of vertices, maximal among independent subsets of S. Let D0 = DnN(I), a = a(D;I) = (< D0 >), and b = b(D;I) = min[jS0j; S0 S and D0 N(S0)]. Then a+c b jD0j. Proof Note that because 0(G) > (G), G does not have Property DI and therefore, by Corollary 2.1, D0 is necessarily nonempty. Also, because G has no isolated vertices, every vertex in D must have a neighbor outside of D, i.e., in S. Therefore b is well de ned, and b jD0j. Let S0 S satisfy jS0j = b and D0 N(S0). Then I\S0 = ;, and I[S0 dominates G. Therefore (G) + c = 0(G) jI[S0j = jIj+jS0j = jIj+ b (G) a + b, using the 15 obvious inequalityjIj+a (G). Rearranging, (G)+c (G) a+b, we have a+c b. Corollary 2.5 In the circumstances of Lemma 2.3, jD0j a + c 1 + c 2 and must have at least c 1 edges. Proof The rst assertion follows directly from the conclusion of Lemma 2.3. The second assertion arises from the fact that adding an edge to a graph can decrease its independence number by at most one, so, sincejD0j c a = (), must be obtained from the empty graph on jD0j vertices by inserting at least c edges. Theorem 2.4 If G has no isolated vertices and (G) 4 then 0(G) (G). Proof Suppose, on the contrary, that c = 0(G) (G) 1. By Corollary 2.3, (G) = 3 or 4. First suppose that (G) = 3 and that D =fx;y;zg is a minimum dominating set in G. Let S = V nD, and let Nx = N(x)\S, Ny = N(y)\S, and Nz = N(z)\S. By Corollary 2.5, every set I maximal among independent subsets of S must be contained in only one of Nx, Ny, Nz { otherwise, the corresponding D0 would have at most one element. From this observation it follows that Nx, Ny, Nz are disjoint, and that any two vertices not in the same set, among these, must be adjacent. Therefore, taking one vertex from each of Nx, Ny, Nz, we obtain a dominating set of size 3 in S = V nD, whence 0(G) 3 = (G) (G), contrary to supposition. Now suppose that (G) = 4 and D =fx1;x2;x3;x4gis a minimum dominating set in G. As above, let S = VnD and Ni = N(xi)nD = N(xi)\S, i = 1;2;3;4. The Ni are nonempty because G has no isolated vertices. By Corollary 2.5, each maximal independent subset of S can dominate at most 2 elements of D, and so the same is true of any independent subset of S. We show that there must exist i;j, 1 i < j 4, and u2Ni, v2Nj, such that u;v are not adjacent. If not, then for every such i;j, every edge uv, u2Ni, v2Nj, u6= v, is 16 an edge of G. Choosing a representative from each Ni, we obtain a dominating set with no more than 4 elements in V nD, whence 0(G) 4 = (G) (G), contrary to supposition. So, without loss of generality, suppose that u2N3;v 2N4, u6= v, and u and v are not adjacent. Let I be any maximal independent subset of S containing u and v. Then I (N3[N4)n(N1[N2), and the D0 of Lemma 2.3 is fx1;x2g. Then u;v62N1[N2 and u;v must dominate N1[N2. Further, with a;b as in Lemma 2.3, by Lemma 2.3 we have that 2 a + c b jD0j = 2. We conclude that a = c = 1 and b = 2. Therefore N1\N2 = ; (because b = 2), and x1x22E(G) (because a = 1). Now, if y2N1 and z2N2 were not adjacent, then by the reasoning applied to u and v, y;z must dominate N3[N4, and so u;v;y;z would be a dominating set in G in S = V nD, whence 0 = , again contrary to supposition. So every edge yz, y 2N1, z 2N2, is in G. Choose any y2N1. Then D0 =fx1;y;x3;x4g is a minimum dominating set, because x1x2 2E(G) and y dominates N2. But then u;v;x2 is an independent set in S0 = V nD0 which dominates 3 elements of D0, namely x1, x3, and x4, which is impossible by Corollary 2.5. 17 Chapter 3 DI-Pathological Graphs 3.1 Minimal DI-Pathological Graphs with Domination Number Three A graph G is said to be DI-pathological if every minimum dominating set in G intersects every maximally independent set of G. In other words, G is DI-pathological if and only if G does not have property DI de ned in Chapter two. Therefore the result in Theorem 2.3 could be restated as follows: for graphs G with no isolated vertices and with (G) = 2, G is DI-pathological if and only if G = Km;n for some m;n 3. In this section, we nd the DI-pathological graphs with domination number three with the least number of vertices and edges. First of all, it is a trivial fact that if a graph has an isolated vertex, then certainly every minimum dominating set must intersect every maximally independent set at that vertex. Therefore, technically, the graph with the least number of vertices or edges and that has domination number three and is DI-pathological is the complement of K3. Our interest, however, is in DI-pathological graphs with no isolated vertices. Now, if we restrict our graphs to those with no isolated vertices, then at least one component of the graph must be DI-pathological if the whole graph is DI-pathological. As noted before, if (G) = 1, then G is not DI-pathological. Therefore, among those disconnected graphs of domination number three with no isolated vertices that are DI- pathological, every one must have some component H such that (H) = 2 and H is DI- pathological. By the statement above, H = Km;n for m;n 3. Therefore, the smallest disconnected DI-pathological graph with domination number three and no isolated vertices 18 is K3;3 + K2. And every such graph is of the form Km;n + (K1_H), m;n 3, with _ denoting the join operation and H nonvoid. Now we will turn our attention to connected DI-pathological graphs of domination number three. De nition 3.1 Let D be a minimum dominating set of a graph G. Let x 2 D. Then, the D-private neighborhood of x, written PD(x), is fv2V(G)nD : v2N(x) and v62N(Dnfxg)g. In other words, PD(x) is the collection of vertices outside of D which are dominated only by one vertex, x, of D. Vertices of PD(x) are called D-private neighbors of x. Lemma 3.1 If D is a minimum dominating set in G, and J V(G)nD is an independent set such that D N(J), then G is not DI-pathological. Proof Suppose D is a minimum dominating set in G, and J V(G)nD is an independent set such that D N(J). Then let I be a maximally independent subset of V(G)nD such that J I. Because I is a maximally independent subset of V(G)nD, (V(G)nD) N(I), and since J I, D N(I). Therefore I is maximally independent in G, and D\I =;, so G is not DI-pathological. Remark: Lemma 3.1 is a restatement of Corollary 2.1. Theorem 3.1 Let G be a connected DI-pathological graph with (G) = 3, and let D be a minimum dominating set in G. Then for all x2D,jPD(x)j 2: Proof Let D = fx1;x2;x3g be a minimum dominating set for G, and let S = V(G)nD. First, assume jPD(x1)j= 0. Then N(x1)\S [N(x2)[N(x3)]\S, and since D is minimum, x1x2;x1x3 62E(G). Pick v2N(x1). Such a v exists because G is connected. Without loss of generality, since jPD(x1)j= 0, say v2N(x2). Then D1 :=fv;x2;x3g is another minimum dominating set. 19 Now, consider the subgraph ^G := < V(G)nfx1g>. Certainly fx2;x3g is a minimum dominating set of ^G. Claim: ^G has no minimum dominating set and maximal independent set which are disjoint. Suppose ^D and ^I were such a pair of a minimum dominating set and a maximally independent set for ^G. Then v 62 ^D since if it were, then ^D would dominate G implying that (G) < 3. Also, no vertex in NG(x1) is in ^I: otherwise, ^I would be an independent dominating set in G disjoint from ^D[fx1g, a minimum dominating set of G. This cannot be, since G is DI-pathological. Therefore ^D[fvg is a minimum dominating set for G, and ^I[fx1g is an independent dominating set in G. This again contradicts the fact that G is DI-pathological. Hence no such ^D and ^I exist and the claim is true. Thus ^G is DI-pathological with no isolated vertices and ( ^G) = 2, and hence ^G is a complete bipartite graph with parts of size at least 3, by Theorem 2.3. Thereforefx2;x3gare in di erent parts of ^G. Now, since ^G is a complete bipartite graph and v2NG(x1)\NG(x2), fx2;vg is a minimum dominating set for G which is a contradiction since (G) = 3. Thus jPD(x1)j6= 0. Now suppose jPD(x1)j= 1. Say PD(x1) =fvg. Let ^D =fv;x2;x3g. Note that ^D is also a minimum dominating set for G. Now x1x2;x1x362E(G) since otherwise ^D would be a minimum dominating set such that jP^D(v)j= 0, and, as shown above, jP^D(v)j> 0. Now, suppose there exists u 2 N(x2)\N(x3)\S. Then fug must dominate N(x1) since otherwise G would not be DI-pathological; if w 2 N(x1)nN(u) then J = fu;wg is an independent set in V(G)nD such that D N(J), whence Lemma 3.1 delivers the contradictory conclusion. In particular, uv2E(G). But thenfugdominates ^D, a minimum dominating set of G, giving rise to a contradiction again, by Lemma 3.1, since G is DI- pathological. Therefore N(x2)\S\N(x3) =;. Since jPD(xi)j 1, i = 2;3, both N(x2)\S and N(x3)\S must be nonempty, so let p2N(x2)\S and let q2N(x3)\S. 20 Suppose p and q are non-adjacent. Then pv;qv 62E(G) since otherwise fp;qg would be an independent set disjoint from ^D dominating ^D. Therefore fp;q;vg V(G)nD is independent and dominates D, giving rise to a contradiction, and hence no such pair of nonadjacent vertices p and q exist. Therefore, if p2N(x2)\S, fpg dominates N(x3)\S, and similarly if q2N(x3)\S, fqg dominates N(x2)\S. Thus fp;q;vg is a minimum dominating set. This implies that x2x32E(G) since if not thenfx1;x2;x3gwould be an independent set dominatingfp;q;vg. Since G is connected, there exists some edge connecting fx1;vg to N[fx2;x3g]. Suppose x1p2E(G) where without loss of generality p is some vertex of N(x2)\S. Then fx2;p;vg is a minimum dominating set. x1 dominates fp;vg, and therefore x1 cannot be nonadjacent to any vertex of N(x2)\S. Therefore x1 dominates N(x2)\S. This implies fx1;x3g is a dominating set for G of size two which contradicts (G) = 3. The same contradiction is reached if we say vp2E(G) or if x1q or vq2E(G) for some q 2 N(x3)\S. Thus since G is connected, and one of these edges must exist, this is a contradiction. Therefore jPD(x1)j6= 1, and hence jPD(x)j 2 for all x2D. Corollary 3.1 If G is a connected DI-pathological graph with (G) = 3, thenjV(G)j 9. Proof For all x;y in a minimum dominating set D, jPD(x)j 2, and PD(x)\PD(y) = ;. Since there are three vertices in D, jV(G)j 9. Corollary 3.2 The graph G in Figure 3.1 is the unique connected, DI-pathological graph with (G) = 3, with the least number of vertices and edges. Proof First, to see that G is indeed DI-pathological, note that it has a unique minimum dominating set offx1;x5;x9g. Now if there were some maximally independent set I disjoint from fx1;x5;x9g, then it must contain either x4 or x6. Without loss of generality, say that 21 x1 x2 x3 x4 x5 x6 x7 x8 x9 Figure 3.1: G I contains x4. Then I cannot be independent and dominating without having x1 as one of its vertices. Therefore G is in fact DI-pathological. Note also that G is connected, and (G) = 3. By Corollary 3.1, G has the minimum number of vertices that any such graph could have. Now suppose that H is connected, DI- pathological on 9 vertices, (H) = 3, and E(H) 10. We aim to show that H = G. This will show not only that G is the unique connected DI-pathological graph with domination number 3 with the least number of edges among those with the least number of vertices, 9, but also that G is the unique such graph with the least number of vertices among those with the least number of edges, which is 10. To see this, suppose it has been shown that H = G. It then follows that the minimum number of edges in a connected DI-pathological graph with domination number 3 is 10, because, by showing H = G it is shown that among such graphs with 9 vertices the minimum number of edges is 10, and any graph with 10 or more vertices and 9 or fewer edges is either disconnected or a tree; by Theorem 2.1, every tree with domination number 3 is not DI-pathological. Let D =fx1;x2;x3g be a minimum dominating subset of V(H). By Theorem 3.1, and the fact that jV(G)j= 9, the other six vertices in H are u1;u2 2N(x1)n(N(x2)[N(x3)), v1;v2 2N(x2)n(N(x1)[N(x3)), and w1;w2 2N(x3)n(N(x1)[N(x2)). So H looks like Figure 3.2 with at most four edges yet to be added. To see that fu1;u2g, fv1;v2g, and fw1;w2g are independent suppose that, say, u1u2 2 E(H). Then D0 :=fu1;x2;x3g is a minimum dominating set in H. If some edge viwj is not 22 x1 x2 x3 u1 u2 v1 v2 w1 w2 Figure 3.2: H minus 4 edges in H, thenfx1;vi;wjgis an independent set of vertices dominating D0 contradicting that H is DI-pathological. Therefore all four edges viwj are in H. But, with u1u2 as an edge, that implies that jE(H)j 11 which is a contradiction. Let K = H D. Then K is tripartite with partsfu1;u2g,fv1;v2g, andfw1;w2gand at most four edges. First of all, K contains no isolated vertices. To see this, suppose that, say, u1 is isolated in K. Then because H is DI-pathological, every edge viwj is in H. (Otherwise, there would be an independent set in V(H)nD which dominates D.) But then there would be ten edges in H, and no edge from fx1;u1;u2g to the rest of H, contradicting that H is connected. Now if jE(K)j< 4, then since K has no isolated vertices, there must be three edges forming a perfect matching in K. If this were the case, however, there would be an inde- pendent set I V(H)nD such that I would dominate D in H contradicting that H is DI-pathological. Therefore jE(K)j= 4. There exists a vertex of K, say u1, such that deg(u1) = 1. And, without loss of gener- ality say that u1v12E(K). If wiv262E(K), i2f1;2g, then fwi;v2;u1g V(H)nD would be an independent set of vertices of H D dominating D. Therefore w1v2;w2v2 2E(K). Since jE(K)j = 4, and u2 is not isolated, w1v1;w2v1 62 E(K). If u2v1 62 E(K), then fu2;v1;w1g V(G) nD would be an independent set of H dominating D. Therefore u2v12E(K); K must be isomorphic to the graph in Figure 3.3 and H = G. 23 u1 w1v1 u2 v2 w2 Figure 3.3: K De nition 3.2 Let Bn for n 3 be the graph of two 4-cycles joined by a path of length 3n 7. Notice that B3 is the graph G in Figure 3.1. Also following the same basic argument in Corollary 3.2, Bn has a unique minimum dominating set of size n, and Bn is clearly DI- pathological for all n 3. These observations lead to the following conjecture. Conjecture The unique connected, DI-pathological graph G with the fewest number of edges and the fewest number of vertices such that (G) = n is Bn for n 3. 3.2 DI-Pathological Graphs De nition 3.3 Let H be a simple graph. An exploded H is a graph G such that for all v 2 V(H), v is replaced by an independent set Av of size at least one, and every vertex of Av is adjacent to every vertex ofAu if and only ifv is adjacent touinH. Gcan also be called an explosion ofH. De nition 3.4 n 24 n is the class of graphs such that G2 n if and only if G is an explosion of a path on n vertices. De nition 3.5 n n is the class of graphs such that G2 n if and only if G is an explosion of a cycle on n vertices. Hereafter, if G2 n[ n, the independent sets replacing vertices in the path or cycle of which G is an explosion will be listed A1;:::;An corresponding to vertices around the cycle or along the path, starting at an end. In the case of cycles, the indices i on the Ai are adjusted mod n. Lemma 3.2 Suppose that H is a graph with no isolated vertices and G is an explosion of H, with independent sets Av replacing the vertices v2V(H). If I is a maximally independent set of vertices of G, v2V(H), and I\Av6=;, then Av I. Proof Since I is maximally independent, I is dominating in G. Suppose that a2Av\I and b2AvnI. Because I is independent, and a2I, I can contain no vertices of any Au, u a neighbor of v in H. But then b62NG[I], contradicting the fact that I is dominating in G. Corollary 3.3 With H, G, and the Av as in the previous lemma, I V(G) is maximally independent in G if and only if for some maximally independent J V(H), I =[v2JAv. Lemma 3.3 With H, G, and the Av, v2V(H) as in the previous lemma, if D is a minimal dominating set in G then for all v2V(H), either Av D orjAv\Dj 1. Proof IfjD\Avj 2, then clearly, deleting one vertex of D\Av from D would result in a dominating set which is a proper subset of D unless the deleted vertex and thus every vertex of D\Av dominates only itself. Therefore, jD\Avj 2 implies Av D. 25 Lemma 3.4 With H, G, and the Av, v2V(H), as previously, if v2V(H),jAvj 3, and D is a minimum dominating set for G, thenjD\Avj 1. Proof By Lemma 3.3, if jD\Avj > 1 then Av D. If Av D, then exchanging two vertices of Av for one vertex of some Au, u2NH(v), gives a smaller dominating set in G than D. Lemma 3.5 Let H, G, and the Av, v 2V(H), be as previously. Suppose v 2V(H) and jAvj 3. If D is a minimum dominating set for G, and D\Av 6= ;, then there exists u2NH(v) such that Au\D6=;. Proof Suppose d 2 D\Av. By Lemma 3.4, (Avnfdg)\D = ;. Therefore, since D is dominating, there exists some u2NH(v) such that Au\D6=;. Recall that a set D V(G) is totally dominating if and only if V(G) = N(D), and that the total domination number is de ned to be t(G) = min[jDj: D is a totally dominating set of V(G)]. Corollary 3.4 If H is a graph with no isolated vertices, and G is an explosion of H with jAvj 2 for all v 2V(H), then (G) = t(H). If S is a minimum total dominating set in H and D V(G) is formed by taking one representative from Av for each v2S, then D is a minimum dominating set in G. If jAvj 3 for all v2V(H), then every minimum dominating set D of G is obtained as described above, by choosing one representative from Av for each v in some minimum total dominating set in H. Proof Suppose S is a minimum total dominating set in H and D is formed as described. Label the vertex of D that is a representative of Av, ^v. First, to see that D is a dominating set in G, note that for each v2S, NG(^v) =[fAu : u2NH(v)g. Since S is total dominating 26 in H,[fN(v) : v2Sg= V(H), and hence D is indeed dominating in G. Therefore, since a total dominating set in H gives rise to a dominating set in G of the same size, (G) t(H). Suppose D is a minimum dominating set in G. Let ~S V(H) be the set fv2V(H) : D\Av 6= ;g. By Lemmas 3.3 and 3.4, any Av such that D\Av 6= ; must be such that jD\Avj2f1;2g. Therefore, if jAvj 3 for all v2V(H), D consists of one representative of each Av, v2 ~S. If v 2 ~S, and jAvj = jD\Avj = 2, then another minimum dominating set in G may be obtained by replacing one vertex of D in Av by a vertex in Au for some u adjacent to v in H. (Because D is minimum dominating and Av D, jAvj = 2, no such Au can contain a vertex in D.) Continuing in this way we obtain another minimum dominating set for G at most one vertex from each Aw, w2V(H). Let us continue to call this set D, and let ~S be de ned as before. Note that if jAwj 3 for all w2V(H), then the new D is the D we started with. It remains only to show that ~S is a total dominating set in H, for then we have that t(H) j~Sj=jDj= (G), so t(G) = (G) and every D formed in G from a minimum total dominating set in H as described is minimum dominating in G. Also, by previous remarks, ifjAvj 3 for all v2V(G), every minimum dominating set in G must be obtainable in this way. But it is quite clear that ~S is a total dominating set in H, for if w2V(H)nNH( ~S) then no vertex in Aw is in NG(D); since V(G) = NG[D], it would follow that Aw D, but jAwj 2 and arrangements have been made so that jAw\Dj 1. Lemma 3.6 Let H, G, and the Av, v2V(H), be as previously, and suppose that H is a path or cycle of order n. Suppose that D V(G), and for some i2f1;:::;ng, D\Aj6=; for all j2fi;i + 1;i + 2g. Then every maximal independent set of vertices in G intersects D. 27 Proof If I were a maximally independent set of vertices of G disjoint from D, then by Lemma 3.2 I\Aj =;, j = i;i+ 1;i+ 2. But then I[Ai+1 is an independent set of vertices properly containing I. Lemma 3.7 Let H, G, and the Av, v2V(H), be as previously, H a path or cycle of order n, n 6, andjAvj 3 for all v2V(H). If D is a dominating set in G such that there exist six consecutive integersfi;i+ 1;i+ 2;i+ 3;i+ 4;i+ 5g, 1 i n 5, such that Aj\D6=;, j 2fi;i + 1;i + 4;i + 5g and Aj\D = ;, j 2fi + 2;i + 3g, then there is no maximally independent (and hence dominating) subset of V(G) disjoint from D. If H is a cycle, the same holds without the requirement 1 i n 5, reading indices mod n. Proof By Lemma 3.2 if there existed a dominating independent set I of G disjoint from D, then I\Ai+26=; in order that I dominate Ai+1. But, by the same argument, I\Ai+36=; in order that I dominate Ai+4. This is a contradiction because I is independent. The following lemma is only true for graphs G2 n. Lemma 3.8 If G 2 n, n 2, and D is a minimum dominating set in G such that D\A16=;andjA1j 3 or D\An6=;andjAnj 3, then no maximally independent subset of V(G) is disjoint from D. Proof If, say, jA1j 3 and D\A1 6= ;, then by Lemma 3.5 D\A2 6= ;. By Lemma 3.2, if I is a maximal independent set of vertices of G disjoint from D then I\Ai =;, i = 1;2. But then I[A1 is an independent set in G properly containing I. Theorem 3.2 If G2 n, an explosion of H = Pn, n 2, n6= 4;7;10, andjAvj 3 for all v2V(H), then G is DI-pathological. 28 Proof If n = 2, then G = Km;n for some m;n 3. By Theorem 2.2, G is DI-pathological. Since jAvj 3 for all v2V(H), by Corollary 3.4 D is formed by choosing one vertex from each Av, v 2S, where S is a minimum total dominating set in H = Pn. If n = 3, then any minimum dominating set D for G must have the property that either D\A1 6= ; or D\A36=;. In either case, by Lemma 3.8, G is DI-pathological. Now, if n 5, then we must consider three cases. (i) n 0(mod 4) Note that since n6= 4, n 8. Any minimum total dominating set S of Pn has the property that there exist six consecutive vertices of Pn,fi;i+ 1;i+ 2;i+ 3;i+ 4;i+ 5g such that fi;i + 1;i + 4;i + 5g2S. The conclusion that G is DI-pathological now follows from Corollary 3.4 and Lemma 3.7. (ii) n 1(mod 4) Any minimum total dominating set S of Pn has the property that there are three consecutive vertices, fi;i + 1;i + 2g2S. Thus in any minimum dominating set D of G, there must exist a set of three consecutive integersfi;i+ 1;i+ 2gwith the property that D\Ai;D\Ai+1;D\Ai+26=;. By Corollary 3.4 and Lemma 3.6, no maximally independent set of V(G) could be disjoint from D. (iii) n 2;3(mod 4) Here, any minimum total dominating set S of Pn falls into at least one of the following two categories. (a) There exist three consecutive integers fi;i + 1;i + 2g 2 S. In this case, by Corollary 3.4 and Lemma 3.6 there is no maximally independent set disjoint from any minimum dominating set D in G, derived from such an S. (b) As long as n 6= 7;10, either f1g S, fng S, or there exist six consecutive vertices of Pnfi;i+ 1;i+ 2;i+ 3;i+ 4;i+ 5gsuch thatfi;i+ 1;i+ 4;i+ 5g S. 29 By Corollary 3.4 and Lemmas 3.8 and 3.7, no maximally independent subset of V(G) is disjoint from any minimum dominating set D derived from such an S. In every case there is are no minimum dominating sets which are disjoint from any maximally independent sets. Thus G is DI-pathological. Theorem 3.3 If G2 n, n 4, n6= 6, andjAvj 3 for all v2V(H) where H = Cn, then G is DI-pathological. Proof Let G2 n as above. As in the proof of the previous theorem, by Corollary 3.4 any minimum dominating set D of G will be formed by choosing one representative from each of the sets Av v2S, a minimum total dominating set of H. We must consider the following three cases. (i) n 0(mod 4) Whenn = 4, G Kr;s, r;s 6, so assumen 8. Any minimum total dominating setS of Cn is such that there exists six consecutive vertices of Cnfi;i+1;i+2;i+3;i+4;i+5g such that fi;i + 1;i + 4;i + 5g S. Thus any minimum dominating set D of G will be such that Ai, Ai+1, Ai+4, Ai+5 \D6=;and Ai+2, Ai+3 \D =;. By Lemma 3.7, no maximally independent set exists which is disjoint from D. (ii) n 1(mod 4) Any minimum total dominating set S of Cn is such that there are three consecutive vertices of Cn,fi;i+ 1;i+ 2g S. By Lemma 3.6, there is no maximally independent set disjoint from any minimum dominating set D in G. (iii) n 2;3(mod 4) Note that since n6= 6, n 7. Therefore, a minimum total dominating set S in H = Cn falls into at least one of the following two categories. 30 (a) There exist three consecutive vertices of Cn, fi;i + 1;i + 2g S. In this case, by Lemma 3.6 there is no maximally independent set disjoint from any minimum dominating set D derived from such an S. (b) There exist six consecutive vertices of Cn, fi;i + 1;i + 2;i + 3;i + 4;i + 5g, such thatfi;i+ 1;i+ 4;i+ 5g S. By Lemma 3.7, no maximally independent subset of V(G) exists that is disjoint from any minimum dominating set D derived from such an S. In every case, there are no minimum dominating sets which are disjoint from any maximally independent sets. Therefore G is DI-pathological. Since it has been shown that many exploded paths and cycles are DI-pathological, it is natural to examine if other graphs can be exploded giving rise to other DI-pathological graphs. It turns out that many graphs may fall into this category. In fact, it is an easy exercise to see that even any exploded Petersen graph withjAvj 3 for all vertices v is also DI-pathological. Another natural question would be if all DI-pathological graphs could be characterized as explosions of simple graphs. It will be shown that this is not the case. In fact the theorem below shows that DI-pathological graphs of a certain size can take various forms. De nition 3.6 A graph G is said to have an exploded tail of length n if there exists S V(G) such that = H2 n for some n, and the only edges connecting S to V(G)nS are incident to vertices of A1 S. De nition 3.7 A graph G is said to have an exploded ear of length n if there exists S V(G) such that 31 = H2 n for some n, and the only edges connecting S to V(G)nS are incident to vertices in either A1 or An S; and there is at least one edge with an end in Ai and the other end in V(G)nS, for each i2f1;ng. Theorem 3.4 If G is a simple graph with an exploded tail of order n1 12 or an exploded ear of order n2 14, and withjAij 3, i = 1;2;:::;nj, j = 1;2, then G is DI-pathological. Proof Let G be such a graph, and let D be a minimum dominating set for G. Clearly, whether G has an exploded tail of order n1 12 or an exploded ear of order n2 14, there must exist six consecutive integers fi;i + 1;i + 2;i + 3;i + 4;i + 5g such that Aj\D6= ;, j2fi;i+ 1;i+ 4;i+ 5g, and Ai+2\D = Ai+3\D =;. By the same logic as in Lemma 3.7, there is no maximally independent set for G that is disjoint from D. At rst glance, it may seem that in the previous theorem the requirement that n1 12 and n2 14 is a little bit of an overkill. However, we have found that these are optimal bounds for n. In other words, there are non-DI-pathological graphs such that they an exploded tail of order 11, and there are also non-DI-pathological graphs such that they have an exploded ear of order 13. Two such graphs are given in Figures 3.4 and 3.5. Figure 3.4: A non-DI-pathological graph G with an exploded tail of order 11 It can clearly be seen that the graph G in Figure 3.4 has an exploded tail of order 11, and it is not di cult to verify that (G) = 7. Thus the vertices that are boxed form a minimum dominating set that is, in fact, disjoint from the maximally independent set of vertices that are circled. The graph H in Figure 3.5 has an exploded ear of order 13, and 32 Figure 3.5: A non-DI-pathological graph H with an exploded ear of order 13 (H) = 8. As before, it is clear to see that the boxed vertices form a minimum dominating set disjoint from the maximally independent set of vertices that are circled. The previous theorem sheds some light on how di cult it would be to classify all DI- pathological graphs. The "non-tail" or "non-ear" part of the graph could be almost anything. One also notices that every DI-pathological graph mentioned so far in this paper has at least one set of clones, where two vertices x and y are called clones in G if N(x) = N(y). So it may seem that the existence of clones might be a necessity for DI-pathological graphs. Even this characteristic is not shared by all DI-pathological graphs. For example, the graph of two cycles on 7 vertices joined by a path of length 2 is DI-pathological but has no clones. In fact if G is the graph composed of two cycles, Cm and Cn joined by a path of length k where m;n> 4, m;n 1(mod 3), and k 2(mod 3), then G is DI-pathological and has no clones. 33 Chapter 4 The Principle of Strong Duality and the Principle of Complementary Slackness In Chapter 1 were introduced many fractional analogues to such parameters as the dom- ination number, the total domination number, the inverse domination number, the closed neighborhood packing number, the open neighborhood packing number, and the indepen- dence number. Since the problems of nding these parameters can be viewed as integer programs and the problems of nding their fractional analogues can be viewed as linear programs, an extremely helpful tool is the Principle of Strong Duality. This is the central result in the theory of linear programming, and a thorough examination of application of the Principle of Strong Duality and its application to fractional graph theory can be found in [11]. Here we purloin from [11] the basic de nitions and results in linear programming pertinent to our aims. A linear program (LP) is an optimization problem that can be expressed in the form "maximize ctx subject to Ax b", where b is an m-vector, c is an n-vector, A is an m- by-n matrix, and x varies over all the n-vectors with nonnegative entries. (Inequalities are coordinate-wise.) The problem "minimize ctx subject to Ax b" is also a linear program; again, we assume that x 0. It is easy to see that problems with equality constraints or with unconstrained variables can be put into the above form, so these variations may be considered. For our purposes, LPs always take the standard forms introduced here. An integer program (IP) is an optimization problem of the same form as a linear program except that the vector x is subject to the additional constraint that all its entries must be integers. In an LP or an IP, the expression ctx is called the objective function, a vector x satisfying the constraints Ax b, x 0 is called a feasible solution, and the optimum of the objective 34 function over all feasible solutions is called the value of the program. It is natural to assign the value 1 to a maximization program with no feasible solutions and the value +1 if the objective function is unbounded on feasible solutions. The linear program obtained from an integer program P by dropping the constraint that the entries of x be integers is called the linear relaxation of P. If P is the (linear or integer) program "maximize ctx subject to Ax b, x 0", then the program "minimize bty subject to Aty c, y 0" is called the dual of P. If x is a feasible solution for P and y is a feasible solution for the dual of P, then because x, y 0, we have the weak duality inequality. ctx = xtc xtAty = (Ax)ty bty This implies that the value of P is less than or equal to the value of the dual of P. In fact, if P is a linear program, more is true. Theorem 4.1 The Principle of Strong Duality A linear program and its dual have the same value. 4.1 The Fractional Domination Number and the Fractional Closed Neighbor- hood Packing Number For a graph G, the domination number, (G), and the closed neighborhood packing number, (G), were de ned in Chapter 1. The problem of nding (G) and (G) are dual integer programs. Consequently, the problem of nding their fractional analogues, f(G) and f(G) are dual linear programs. By the Principle of Strong Duality, therefore, f(G) = f(G). When attempting to nd f(G) or f(G) for a graph G, one need only nd two functions g;h : V(G)![0;1] such that g is fractional dominating, h is a fractional closed neighborhood packing function, and Pv2V(G)g(v) = Pv2V(G)h(v). This then immediately shows that g is minimum, h is maximum, and Pv2V(G)g(v) = Pv2V(G)h(v) = f(G) = f(G). 35 v z w xy Figure 4.1: G It then becomes a simple exercise to nd f(G) for a graph G such as Figure 4.1, which is a copy of the C5 with a chord, that was represented in Figure 1.2 in Chapter 1. Recall the function f1 : V(G) ! [0;1] from Chapter 1 such that f1(v) = 0, f1(z) = f1(w) = 12, and f1(y) = f1(x) = 14 which is clearly fractional dominating. In Chapter 1, the claim was made that f1 was minimum and therefore that f(G) = Pu2V(G)f1(u) = 32. To now verify this, consider the fractional closed neighborhood packing of G, h : V(G)![0;1], de ned by h(v) = h(z) = h(x) = 12 and h(w) = h(y) = 0. Since Pu2V(G)h(u) = 32 as well, f(G) does indeed equal 32. v z w xy 12 12 v z w xy 12 f1 h 12 12 01414 0 0 Figure 4.2: f1, a fractional dominating functions and h, a fractional closed neighborhood packing 36 4.2 The Fractional Total Domination Number and the Fractional Open Neigh- borhood Packing Number For a graph G with no isolated vertices, the problem of nding the total domination number, t(G), also has an integer dual, and it is the problem of nding the open neigh- borhood packing number, 0(G). And, just as in the previous section, the problem of nd- ing their fractional analogues ( t)f(G) and 0f(G) are dual linear programs. Therefore the problem of nding ( t)f(G) for a graph G with no isolates simpli es into nding functions g;h : V(G) ! [0;1] such that g is a fractional total dominating function, h is a fractional open neighborhood packing, and Pv2V(G)g(v) = Pv2V(G)h(v). This sum is then the frac- tional total domination number and the fractional open neighborhood packing number. To see an example, consider the cycle on 5 vertices, C5. In Chapter 1, the claim was made that g : V(C5) ! [0;1] de ned by g(u) = 12 for all u2C5 is a minimum fractional total dominating function. This becomes obvious when one notices that g is also a fractional open neighborhood packing of C5. In fact, it will be seen in Chapter 5 that g is the only fractional total dominating function and the only fractional open neighborhood packing for C5. Thus clearly ( t)f(C5) = 0f(C5) = 52. 1212 12 12 12g Figure 4.3: g, a fractional total dominating function and a fractional open neighborhood packing for C5 The example in Figure 4.3 helps to illustrate the following theorem. Theorem 4.2 For n 3, ( t)f(Cn) = n2. Proof The function g : V(Cn) ! [0;1] de ned by g(u) = 12 for all u2Cn is both a min- imum fractional total dominating function and a fractional open neighborhood packing of 37 Cn. Thus, by the principle of strong duality, since Pu2V(Cn)g(u) = n2, ( t)f(Cn) = n2. This next theorem makes use of the principle of strong duality to nd ( t)f(Pn) for n 2. Theorem 4.3 For n 2 ( t)f(Pn) = 8 >>>> >>> < >>> >>> >: n 2 if n 0(mod 4) dn2e if n 1(mod 4) n 2 + 1 if n 2(mod 4) dn2e if n 3(mod 4). Proof For simplicity, label the vertices of Pn sequentially along the path starting at one end as follows: fx1;x2;:::;xng. This proof now divides into four cases. Case 1: n 0(mod 4) Let g : V(Pn)![0;1] such that g(xi) = 8 >< >: 1 if i 2;3(mod 4) 0 if i 0;1(mod 4). g is both a fractional total dominating function and a fractional open neighborhood packing of Pn. Thus, by the principle of strong duality, since Pu2V(Pn)g(u) = n2, ( t)f(Pn) = n2. Case 2: n 1(mod 4) Let g : V(Pn)![0;1] such that g(xi) = 8 >< >: 1 if i 2;3(mod 4), or if i = n 1 0 if i 0;1(mod 4), i6= n 1. Let h : V(Pn)![0;1] such that h(xi) = 8> < >: 1 if i 1;2(mod 4) 0 if i 0;3(mod 4). g is a fractional total dominating function of Pn, and h is a fractional open neighborhood packing of Pn. Thus, by the principle of strong duality, since Pu2V(Pn)g(u) = dn2e = P u2V(Pn)h(u), ( t)f(Pn) =d n 2e. Case 3: n 2(mod 4) Let g : V(Pn)![0;1] such that g(xi) = 8 >< >: 1 if i 1;2(mod 4) 0 if i 0;3(mod 4). 38 g is both a fractional total dominating function and a fractional open neighborhood packing of Pn. Thus, by the principle of strong duality, sincePu2V(Pn)g(u) = n2 +1, ( t)f(Pn) = n2 +1. Case 4: n 3(mod 4) Let g : V(Pn)![0;1] such that g(xi) = 8> < >: 1 if i 1;2(mod 4) 0 if i 0;3(mod 4). g is both a fractional total dominating function and a fractional open neighborhood packing of Pn. Thus, by the principle of strong duality, sincePu2V(Pn)g(u) =dn2e, ( t)f(Pn) =dn2e. 4.3 The Fractional Independence Number, the Fractional Clique-Independence Number, and their Dual Linear Programs The problem of nding the independence number, (G), of a graph G also has an integer dual, and it is the problem of nding the edge covering number, c(G). An edge covering of the graph G is a set of edges E E(G) such every vertex of G is incident to at least one edge of E; c(G) is then the least number of edges in an edge covering. Note that c(G) is de ned only if G has no isolated vertices. The fractional analogue to this is cf(G), the fractional edge covering number. A fractional edge covering is a function : E(G)![0;1] such that for each v 2 v(G), the sum of the weightings of the edges incident with v is 1. Thus cf(G) = minfPe2E(G) (e) : is a fractional edge covering on Gg. The problem of nding f(G) and the problem of nding cf(G) are dual linear programs, and hence f(G) = cf(G). Thus the problem of nding f(G) = cf(G) simpli es into nding a fractional inde- pendent function and a fractional edge covering such thatPv2V(G) (v) = Pe2E(G) (e). To see an example, consider once again the graph G in Figure 4.1. In Chapter 1, the claim was made that the function : V(G) ! [0;1] such that (u) = 12 for all u 2 V(G) is a maximum fractional independent function. In order to see this, consider the function : E(G)![0;1] such that (e)) = 8 >< >: 0 if e is zw 1 2 otherwise . 39 is clearly a fractional edge covering with Pe2E(G) (e) = Pv2V(G) (v) = 52. Therefore f(G) is indeed 52. v z w xy 12 121 2 v z w xy 12 12 ? 12 12 12 12 12 0 ? Figure 4.4: a fractional independent function and a fractional edge covering for G The problem of nding the fractional clique-independence number, ^ f, has the dual linear program of the problem of nding the fractional clique covering number, ^cf. Before we can de ne ^cf, we must rst de ne a fractional clique covering on G. Let K be the set of all cliques of G. A fractional clique covering on G is then a function ^ :K![0;1] such that PK:v2K ^ (K) 1 for all v2V(G). ^cf is de ned to be the minfPK2K ^ (K) : ^ is a fractional clique covering on Gg. In Chapter 1, the claim was made that the function ^ : V(G) ! [0;1] such that ^ (x) = ^ (y) = 1 2 and ^ (z) = ^ (v) = ^ (w) = 1 3 was a maximum clique-independent function on the graph G in Figure 4.1. In order to show that ^ is maximum, we need only nd a fractional clique covering of G, ^ , such that the sum of the weights on the cliques is equal to 2. Thus consider the following function. Let ^ = 8 >< >: 1 if K is fv;w;zg or fy;xg 0 otherwise . ^ is certainly a fractional clique covering since every vertex of G is in a clique that has weight equal to 1. And, since the sum of all the weights on the cliques of G is 2, ^ f = 2. 4.4 The Principle of Complementary Slackness The Principle of Complementary Slackness is an extremely important corollary to the proof of the Principle of Strong Duality, and similarly is a powerful tool in fractional graph theory. Again, a thorough explanation of this topic can be found in [11]. 40 v z w xy 12 v z w xy 12 ?? 13 ?? 11 3 13 1 Figure 4.5: ^ a fractional clique-independent function and ^ a fractional clique covering for G Theorem 4.4 The Principle of Complementary Slackness Let x be any optimal solution to the bounded, feasible linear program, maximize ctx subject to Ax b, x 0, and let y be any optimal solution to the dual, minimize bty subject to Aty c, y 0. Then x (Aty c) = y (Ax b) = 0: It is useful to rewrite this theorem in the contexts in which is will be applied in this thesis. In these restatements, it is important to notice that since x and (Aty - c) are both nonnegative, if some coordinate of x or (Aty - c) is nonzero, then the corresponding coordinate of the other must be zero similarly for y and (Ax - b) . It is also important to note that in all of the cases discussed in this paper, the constraint vector for these linear programs, either b or c, is the vector where 1 is the entry in every component. Thus we have the following corollaries to the Principle of Complementary Slackness. Corollary 4.1 The Principle of Complementary Slackness applied to fractional dominating functions and fractional closed neighborhood packings. Let G be a graph with v 2 V(G). If g(v) > 0 for some minimum fractional dominating function on G, then h(N[v]) = 1 for every maximum fractional closed neighborhood packing h of G; and, if h(v) > 0 for some maximum fractional closed neighborhood packing of G, then g(N[v]) = 1 for every minimum fractional dominating function on G. Corollary 4.1 implies the following two facts: 41 (i) If there exists a maximum fractional closed neighborhood packinghsuch thath(N[v]) < 1, then g(v) = 0 for every minimum fractional dominating function g of G. (ii) If there exists a minimum fractional dominating function g such that g(N[v]) > 1, then h(v) = 0 for every maximum fractional closed neighborhood packing h of G. Corollary 4.2 is almost identical to that of 4.1 and has very similar implications. Corollary 4.2 The Principle of Complementary Slackness applied to fractional total dominating functions and fractional open neighborhood packings. Let G be a graph with v2V(G). If g(v) > 0 for some minimum fractional total dominating function on G, then h(N(v)) = 1 for every maximum fractional open neighborhood packing h of G; and, if h(v) > 0 for some maximum fractional open neighborhood packing of G, then g(N(v)) = 1 for every minimum fractional total dominating function on G. As in Corollary 4.1, Corollary 4.2 implies the following two facts: (i) If there exists a maximum fractional open neighborhood packing h such that h(N(v)) < 1, then g(v) = 0 for every minimum fractional total dominating function g of G. (ii) If there exists a minimum fractional total dominating function g such that g(N(v)) > 1, then h(v) = 0 for every maximum fractional open neighborhood packing h of G. Corollary 4.2 is very useful in the characterization of minimum fractional total domi- nating functions and maximum fractional open neighborhood packings which is much of the aim of Chapter 5. It is worth mentioning that the Principle of Complementary Slackness is applicable to maximum fractional independent functions and maximum fractional clique-independent functions along with their dual linear programs. This topic, however, is not explored in depth in this thesis. 42 Chapter 5 Total Domination Null and Open Neighborhood Packing Null Vertices 5.1 Fractional Total Domination As explained in Chapter 1, a function g : V(G) ! [0;1] is total dominating on G if P v2N(u)g(v) 1 for all u 2 V(G). The fractional total domination number is de ned by ( t)f(G) = minfPv2V(G)g(v): g is a fractional total dominating function on Gg. As mentioned in Chapter 4, the problem of nding 0f(G) is a dual linear program to that of nding ( t)f(G). In [7] the following de nitions of domination null and packing null vertices were given as follows: A vertex v2V(G) is domination null if and only if g(v) = 0 for every minimum fractional dominating function g on G. A vertex v 2 V(G) is packing null if and only if h(v) = 0 for every maximum fractional packing h of G. Continuing the work started in this paper, I de ne two analogous terms corresponding to fractional total dominating functions and fractional open neighborhood packings. A vertex v2V(G) is total domination null if and only if g(v) = 0 for every minimum fractional total dominating function g on G. A vertex v2V(G) is open neighborhood packing null if and only if h(v) = 0 for every maximum fractional open neighborhood packing h of G. For a simple graph G, let GG = fg : V(G) ! [0;1] jg is a minimum fractional total dominating function of Gg, and let HG = fh : V(G) ! [0;1] jh is a maximum fractional open neighborhood packing of Gg. The following lemma is very helpful in the pursuit of characterization of minimum fractional total dominating functions and maximum fractional open neighborhood packings for certain graphs. 43 Lemma 5.1 If there exists a graph G and a function f : V(G)![0;1] such that f(v) > 0 for all v2V(G) and f2GG\HG, thenGG =HG. Proof By the principle of complementary slackness, the following two statements are true. (i) If h2HG then h(N(v)) = 1 for all v 2V(G) since f(v) > 0 for all v 2V(G) and f2GG. Thus h2GG. (ii) If g 2GG then g(N(v)) = 1 for all v 2 V(G) since f(v) > 0 for all v 2 V(G) and f2HG. Thus g2HG. Corollary 5.1 If G is regular of degree k 1, thenGG =HG. Proof Let f : V(G)![0;1] be such that f(v) = 1k for all v2V(G). Clearly f2GG\HG, and f(v) > 0 for all v2V(G). Corollary 5.2 GKr1;r2;:::;rt =HKr1;r2;:::;rt where Kr1;r2;:::;rt is the complete t-partite graph with parts of sizes r1;r2;:::;rt and t 2. Proof Let f : V(G)![0;1] be such that if v is in part i, then f(v) = ( 1t 1)( 1ri). As in the previous corollary, f2GG\HG, and f(v) > 0 for all v2V(G). A similar lemma to that of Lemma 5.1 holds for the sets ^GG := fg : V(G) ! [0;1] jg is a minimum fractional dominating function for Gg and ^HG :=fh : V(G)![0;1] jh is a maximum closed neighborhood packing on Gg. Lemma 5.2 If there exists a graph G and a function f : V(G)![0;1] such that f(v) > 0 for all v2V(G) and f2 ^GG\ ^HG, then ^GG = ^HG. 44 Proof The proof is identical to that of Lemma 5.1, and again comes directly from the prin- ciple of complementary slackness. Similarly, the following corollary comes directly from Lemma 5.2. Corollary 5.3 If G is regular of degree k, then ^GG = ^HG. Also, ^GKr1;r2;:::;rt = ^HKr1;r2;:::;rt where Kr1;r2;:::;rt is the complete t-partite graph with parts of sizes r1;r2;:::;rt and t 2. Proof It is not hard to verify that there exist functions that meet the criteria of Lemma 5.2 for both nontrivial graphs of regular degree and complete t-partite graphs. Also, see [7]. 5.2 Cycles When trying to characterize all functions g2GCn and h2HCn, Lemma 5.1 is extremely helpful. Since Cn is regular of degree 2,GCn =HCn. For simplicity, from now on the vertices of Cn will be labeled fx1;x2;:::;xng sequentially around the cycle. i.e. xnx1 2E(Cn), and xixi+12E(Cn) for all 1 i n 1. Recall that by Theorem 4.2, ( t)f(Cn) = 0f(Cn) = n2. The following theorem totally answers the characterization problem for cycles. Theorem 5.1 If g2GCn and n6 0(mod 4), then g(xi) = 12 for all 1 i n. If g2GCn and n 0(mod 4), then g(xi) = 8> >>> >>> < >>> >>> >: s if i 0(mod 4) 1 s if i 2(mod 4) t if i 1(mod 4) 1 t if i 3(mod 4) where s;t2[0;1]. Proof First, I claim that g2GCn =HCn if and only if g(xi)+g(xi+2) = 1 for all 1 i n where i + 2 is treated as i + 2(mod n). To see this, rst suppose that g(xi) + g(xi+2) = 1 45 for all i. Then g is clearly total dominating on G, and Pni=1g(xi) = n2. Therefore g2GCn. Secondly, let g be any function in g2GCn. Therefore 2Pni=1g(xi) = Pni=1g(xi) +g(xi+2) n = 2 n2 = 2Pni=1g(xi) where the inequality comes from the fact that g(xi) + g(xi+2) 1 for all 1 i n since g is total dominating on G. Thus g(xi)+g(xi+2) = 1 for all 1 i n, and thus the claim is true. Now if n6 0(mod 4), the only way that every pair g(xi) and g(xi+2) can sum to 1 is if g(xi) = 12 for all 1 i n. If n 0(mod 4), however, this is possible only if g(xi) = 8 >>>> >>> < >>> >>> >: s if i 0(mod 4) 1 s if i 2(mod 4) t if i 1(mod 4) 1 t if i 3(mod 4) where s;t2[0;1]. Corollary 5.4 Cn has no total domination null vertices and no open neighborhood packing null vertices for n 3. 5.3 Paths Let n 2. Characterizing GPn and HPn seems to be a much messier problem that it is for cycles. However, the principle of complementary slackness again serves as a valuable tool in this section. For simplicity, from now on, we will refer to the principle of complementary slackness as PCS and label the vertices of Pn sequentially fx1;x2;:::;xng along the path. Lemma 5.3 If v is a stem of G (i.e. v is adjacent to vertex u such that deg(u) = 1) and g is a fractional total dominating function on G, then g(v) = 1. Proof If g(v) < 1, then g would fail to dominate the open neighborhood of u which would be a contradiction to g being a total dominating function on G. 46 Lemma 5.4 Suppose xi is a total domination null vertex in Pn. If i+2 n then g(xi+2) = 1 for any minimum fractional dominating function g on G, and if 1 i 2 then the same holds for xi 2. Proof Suppose xi is as above. Then N(xi+1) is fxi;xi+2g. Thus in order for xi+1 to be dominated by g, g(xi+2) = 1 since g(xi) = 0. Likewise, g(xi 2) = 1 as well. Theorem 5.2 For n 2 the following is the chart of the total domination null and the open neighborhood packing null vertices for Pn. i such that xi is i such that xi is open total domination null neighborhood packing null ( t)f(Pn) n 0(mod 4) i 0;1(mod 4) None n2 n 1(mod 4) i 1(mod 4) i 3(mod 4) dn2e n 2(mod 4) None i 0;3(mod 4) n2 + 1 n 3(mod 4) i 0(mod 4) i 0(mod 4) dn2e Proof First of all, the right most column was shown in Chapter 4. It follows from Lemma 5.3 that GP2 = HP2 = fg : V(P2) ! [0;1] such that g(x1) = g(x2) = 1g, and that GP3 = HP3 = fg : V(P3) ! [0;1] such that g(x1) = t, g(x2) = 1, and g(x3) = 1 t for some t2[0;1]g. The rest of the proof will be divided into 4 parts. Let n 4. n 0(mod 4) If n 0(mod 4), then the constant function h(xi) = 12 for 1 i n is a maximum fractional open neighborhood packing of Pn. Therefore there are no open neighborhood packing null vertices. h also implies that for any minimum fractional total dominating function g, g(N(xi)) = 1 for all 1 i n; this is an application of the PCS. Clearly, g(x1) = g(xn) = 0 by the fact that h(N(xi)) = 12 < 1, i = 1;n. Therefore, again by the PCS 47 conclusions, or using Lemma 5.4, g(x2) = 1 = g(x3), and therefore g(x4) = 0. Thus since the weights on x1;x2;x3;x4 are 0;1;1;0 respectively, the rest follows immediately from the PCS conclusion that g(N(xi)) = 1 for all i, and the only possible member of GPn is the function illustrated in Figure 5.1. ... ...01 0 0 0 0 00 01 11111 1 Figure 5.1: n 0(mod 4) n 1(mod 4) ... ...01 0 0 0 0 00 01 1111 1 11x ia b Figure 5.2: i 1(mod 4), a;b 0, a+b = n 14 In Figures 5.2 through 5.8, a is the number of 4 element sets of vertices that have the same weightings as fx1;x2;x3;x4g, counting from the left, and b is the number of 4 element sets of vertices that have the same weightings as fxn 3;xn 2;xn 1;xng, counting from the right. The function h2HPn illustrated in Figure 5.2 is such that Pu2N(xi)h(u) = 0 < 1 so therefore by PCS, g(xi) = 0 for all g2GPn. Thus xi is total domination null for i 1(mod 4). ... ...01 0 0 0 0 00 01 11 111 11x i 0 011 a b Figure 5.3: i 3(mod 4), a;b 0, a+b = n 54 The function g 2GPn illustrated in Figure 5.3 is such that Pu2N(xi)g(u) = 2 > 1 so therefore by PCS, h(xi) = 0 for all h2HPn. Thus xi is open neighborhood packing null for i 3(mod 4). 48 To see that these are these are the only sets of total domination or open neighborhood packing null vertices consider the following functions g0;g12GPn and h02HPn. g0(xi) = 8> < >: 0 if i 1;2(mod 4), i6= 2 1 if i 0;3(mod 4), i = 2; g1(xi) = 8> < >: 0 if i 0;1(mod 4), i6= n 1 1 if i 2;3(mod 4), i = n 1; h0(xi) = 8 >>> >< >>>> : 0 if i 3(mod 4) 1 if i 1(mod 4) 1 2 if i 0;2(mod 4) n 2(mod 4) ... ...01 0 0 0 00 1 111 11x i 0 011 a b 0 01 11 xi+1 Figure 5.4: i 3(mod 4), a;b 0, a+b = n 64 The functiong2GPn illustrated in Figure 5.4 is such thatPu2N(xi)g(u) = Pu2N(xi+1)g(u) = 2 > 1 so therefore by PCS, h(xi) = h(xi+1) = 0 for all h2HPn. Thus xi is open neighbor- hood packing null for i 0;3(mod 4). ...1 001 101 1 a 0 1 Figure 5.5: a = n 24 The function h 2 HPn illustrated in Figure 5.5 is such that h(xi) = 1 > 0 for all i 1;2(mod 4). Thus the only open packing null vertices are xi such that i 0;3(mod 4). The function represented in Figure 5.4 shows that xi is not total domination null for all i except possibly when i = 1 or when i = n. But, note that the function h2HPn illustrated in Figure 5.5 is also such that h2GPn. Here, h(x1) 6= 0 and h(xn) 6= 0. Thus, it has been shown that there are no total domination null vertices for Pn. 49 n 3(mod 4) ... ...01 0 00 0 001 111 11 x i 01001 1 a b 01 1 Figure 5.6: i 0(mod 4), a;b 0, a+b = n 74 The function h2HPn illustrated in Figure 5.6 is such that Pu2N(xi)h(u) = 0 < 1 so therefore by PCS, g(xi) = 0 for all g2GPn. Thus xi is total domination null for i 0(mod 4). ... ...01 0 0 0 00 01 11 11 1 xi 100 11 a b Figure 5.7: i 0(mod 4), a;b 0, a+b = n 34 The function g 2GPn illustrated in Figure 5.7 is such that Pu2N(xi)g(u) = 2 > 1 so therefore by PCS, h(xi) = 0 for all h2HPn. Thus xi is open neighborhood packing null for i 0(mod 4). The function illustrated in Figure 5.7 shows that xi is not total domination null except when i 0(mod 4) and possibly when i = n. The function illustrated in Figure 5.8 is in GPn, and g(xn) 6= 0. Thus the only total domination null vertices are those xi such that i 0(mod 4). ...1 0 00 1 10 11 a 0 1 xi Figure 5.8: i = n and a = n 34 The function illustrated in Figure 5.6 shows that xi is not open neighborhood packing null except when i 0(mod 4) and possibly when i2f3;ng. The function illustrated in 50 Figure 5.8 is also in HPn, and hence x3 and xn are not open neighborhood packing null. Thus the only open neighborhood packing null vertices are those xi such that i 0(mod 4). Now that it is clear which vertices of Pn are total domination null and which are open neighborhood packing null, we can more easily characterize all functions in the setsGPn and HPn. Theorem 5.3 If n 0(mod 4), then there is only one function in the set GPn, and it is g(xi) = 8 >< >: 0 if i 0;1(mod 4) 1 if i 2;3(mod 4) Proof Let g2GPn. Theorem 5.2 states that g(xi) = 0 for all i 0;1(mod 4). Then, by Lemma 5.4, it must be that g(xi) = 1 for all i 2;3(mod 4). Theorem 5.4 If n 1(mod 4), thenGPn is the set of functions g :fx1;x2;:::;xng![0;1] such that (a) g(xi) = 8 >< >: 0 if i 1(mod 4) 1 if i 3(mod 4) (b) g(x2) = g(xn 1) = 1 (c) Pbn2ck=1g(x2k) =dn4e (d) g(xi) +g(xi+2) 1 for i 0(mod 2). Proof Suppose g2GPn. Part (a) is again a direct result of Theorem 5.2 and Lemma 5.4. Part (b) is direct result of Lemma 5.3. Part (c) is true because ( t)f = dn2e and, by part (a), Pi 3(mod4)g(xi) = bn4c and Pi 1(mod4)g(xi) = 0. Part (d) is obvious since g is a total dominating function on Pn. 51 It is straightforward to see that if g :fx1;x2;:::;xng![0;1] satis es (a) through (d), then g2GPn. Theorem 5.5 If n 2(mod 4), thenGPn is the set of functions g :fx1;x2;:::;xng![0;1] such that (a) Pnk=1g(xk) = n2 + 1 (b) g(x2) = g(xn 1) = 1 (c) g(xi) +g(xi+2) 1 for 1 i n 2. Proof Suppose g2GPn. Part (a) follows from Theorem 5.2 and the de nition of ( t)f(Pn). Part (b) is direct result of Lemma 5.3. Part (c) is obvious since g is a total dominating function on Pn. It is straightforward to see that any g :fx1;x2;:::;xng![0;1] satisfying (a), (b), and (c) is a minimum fractional total dominating function on G. Theorem 5.6 If n 3(mod 4), thenGPn is the set of functions g :fx1;x2;:::;xng![0;1] such that (a) g(xi) = 8 >< >: 0 if i 0(mod 4) 1 if i 2(mod 4) (b) Pbn2ck=0g(x2k+1) =dn4e (c) g(xi) +g(xi+2) 1 for i 0(mod 2). Proof Suppose g2GPn. Part (a) is again the direct result of Theorem 5.2 and Lemmas 5.4 and 5.3. Part (b) is true because ( t)f = dn2e and, by part (a), Pi 2(mod4)g(xi) = dn4e and P i 0(mod4)g(xi) = 0. Part (c) is obvious since g is a total dominating function on Pn. 52 The su ciency of (a), (b), and (c) for g : fx1;x2;:::;xng! [0;1] to be a minimum fractional total dominating function on G is straightforward. Similarly, because of Theorem 5.2, it is not di cult to characterize all of the functions in the set HPn. Theorem 5.7 If n 0(mod 4), thenHPn is the set of functions h :fx1;x2;:::;xng![0;1] such that (a) h(xi) +h(xi+2) = 1 for i 1;2(mod 4) (b) h(xi) +h(xi+2) 1 for i 0;3(mod 2). Proof Let h 2 HPn. Since there are n2 disjoint pairs fxi;xi+2g, i 1;2(mod 4), h is a fractional open neighborhood packing of Pn, and ( t)f(Pn) = 0f(Pn) = n2, each pair fxi;xi+2gmust be such that h(xi)+h(xi+2) = 1, proving (a). Part (b) is a result of h2HPn. On the other hand, it is straightforward to see that if h :fx1;x2;:::;xng![0;1] satis- es (a) and (b) then h2HPn. Theorem 5.8 If n 1(mod 4), thenHPn is the set of functions h :fx1;x2;:::;xng![0;1] such that (a) h(xi) = 8 >< >: 0 if i 3(mod 4) 1 if i 1(mod 4) (b) h(xi) +h(xi+2) = 1 for i 2(mod 4) (c) h(xi) +h(xi+2) 1 for i 0(mod 4) Proof Leth2HPn. To show (a), rst it is clear by Theorem 5.2 thath(xi) = 0 fori 3(mod 4). Also, since there are n 14 disjoint sets of the formfxi;xi+2gsuch that i 2(mod 4), and 53 h2HPn, Pi 0(mod2)h(xi) n 14 . Therefore because 0f(Pn) = Pni=1h(xi) =dn2e, h(xi) = 1 for i 1(mod 4). (b) then follows immediately because 0f(Pn) =dn2e. Finally (c) is a result of the fact that h2HPn. On the other hand, it is straightforward to see that if h :fx1;x2;:::;xng![0;1] satis- es (a), (b), and (c) then h2HPn. Theorem 5.9 If n 2(mod 4), then HPn has only one member, and it is exactly h : fx1;x2;:::;xng![0;1] such that h(xi) = 8 >< >: 0 if i 0;3(mod 4) 1 if i 1;2(mod 4) Proof Let h2HPn. By Theorem 5.2, it is clear that h(xi) = 0 for i 0;3(mod 4). Since 0f(Pn) =dn2e+ 1, it is forced that h(xi) = 1 for i 1;2(mod 4). Theorem 5.10 If n 3(mod 4), then HPn is the set of functions h : fx1;x2;:::;xng! [0;1] such that (a) h(xi) = 8 >< >: 0 if i 0(mod 4) 1 if i 2(mod 4) (b) h(xi) +h(xi+2) = 1 for i 1(mod 4) (c) h(xi) +h(xi+2) 1 for i 3(mod 4), i