Fractional Domination, Fractional Packings, and Fractional Isomorphisms of Graphs Except where reference is made to the work of others, the work described in this dissertation is my own or was done in collaboration with my advisory committee. This dissertation does not include proprietary or classi?ed information. Roberto Ramon Rubalcaba Certi?cate of Approval: Dr. Chris Rodger Professor Mathematics and Statistics Dr. Peter D. Johnson Jr., Chair Professor Mathematics and Statistics Dr. Dean G. Ho?man Professor Mathematics and Statistics Dr. Matthew Walsh Assistant Professor Mathematical Sciences Indiana University?Purdue University at Fort Wayne Stephen McFarland Dean Graduate School Fractional Domination, Fractional Packings, and Fractional Isomorphisms of Graphs Roberto Ramon Rubalcaba 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 13, 2005 Vita Roberto Ramon Rubalcaba was born on December 13, 1975 in San Diego, California, the only child of a single mother, Rosalie Rubalcaba. From a family of hard-working carpenters, his mother encouraged his studies at an early age. He attended San Diego City College summer of 1994. He encountered a mentor, Fabio Martinez, who encouraged him not to stop until he had obtained a doctorate. It was also there that he found aspirations of becoming a teacher, as he spent countless hours as a volunteer tutor. He graduated in the fall of 1996. He later attended San Diego State University where he majored in Mathematics and minored in Geography. In the summer of 1999, he attended a Research Experience for Undergraduates at Auburn University, thanks in part to Robert Grone at SDSU (formerly at AU). It was there that he found the joy of research which resulted in his ?rst paper [15]. He graduated with distinction in August of 1999 and was awarded with the Leadership Award as he encouraged high standards among his peers. He then attended graduate school at Auburn University in the Department of Discrete and Statistical Sciences. In the summer of 2002, he became the ?rst in his family to receive a Masters degree. While at Auburn University he published three more papers [119], [120], [121]. iii Dissertation Abstract Fractional Domination, Fractional Packings, and Fractional Isomorphisms of Graphs Roberto Ramon Rubalcaba Doctor of Philosophy, May 13, 2005 (M.A.M., Auburn University, August 5, 2002) (B.A., San Diego State University, August 20, 1999) (A.A., San Diego City College, December 15, 1996) 140 Typed Pages Directed by Dr. Peter D. Johnson, Jr. The fractional analogues of domination and packing in a graph form an interesting pair of dual linear programs, in that the feasible vectors for both LPs have interpretations as functions from the vertices of the graph to the unit interval. The relationships between the solution sets of these dual problems are investigated. Another pair of dual linear programs, the fractional analogues of total domination and open packing in a graph, also both have interpretations as functions from the vertices to the unit interval. The relationships between the solution sets of these dual problems are also investigated. The fractional analogue of graph isomorphism plays a role in both investigations. Finally, various military strategies are discussed, as well as their fractional analogues. iv Acknowledgments I would like to thank the following people, in no particular order: My mother and father, Rose and Glen Anderson, for their encouragement, support, and his ?nding and correcting of grammatical errors. Steve Hedetniemi, for suggesting the problem of fractional Roman domination, for his encouragement, helpful comments, and suggestions. Wayne Goddard, Pete Slater, and Daniel Ullman, for their helpful comments and suggestions. Matt Walsh, for agreeing to be on the committee, for his suggestions, and for working together on the majority of this dissertation. My advisor, Pete Johnson, for his guidance, suggestions, and encouragement. The Olde Auburn Ale House, for providing Pete Johnson and me with a productive meeting place. Robert Grone, for his comments and for leading me to Auburn University. Robert Bul?n, for agreeing to read the manuscript and for his helpful comments. Chris Rodger and Dean Ho?man, for their observations. Colonel Steve Horton, for his encouragement. Fabio Martinez, for his encouragement and guidance. My ?nac?ee, Clara Ogren, for her love, patience, and support. v Style manual or journal used Discrete Mathematics (together with the style known as ?auphd?). Bibliography follows van Leunen?s A Handbook for Scholars. Computer software used The document preparation package TEX (speci?cally LATEX 2?) together with the departmental style-?le auphd.sty. vi Table of Contents List of Figures x 1 Introduction to Domination, Fractional Graph Theory, and Linear Programming 1 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 De?nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.1 Domination and variations on domination . . . . . . . . . . . . . . . 4 1.2.2 Let?s get fuzzy! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Integer and linear programming . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 New graphs from old . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.1 Graph sums and products . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.2 Graph constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2 Fractional Isomorphisms 19 2.1 Isomorphisms of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Fractional Isomorphisms of Graphs . . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Non-invariants of fractional isomorphisms . . . . . . . . . . . . . . . . . . . 23 2.4 Equitable partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.5 What is the same about fractionally isomorphic graphs? . . . . . . . . . . . 29 2.5.1 An entire class of invariant fractional parameters . . . . . . . . . . . 30 2.6 Graph products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.6.1 Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.7 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3 Minimum Fractional Dominating Functions and Maximum Fractional Packing Functions 39 3.1 Functions which are both minimum fractional dominating and maximum fractional packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2 De?nition of the classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3 The principle of complementary slackness . . . . . . . . . . . . . . . . . . . 41 3.4 A partial classi?cation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.4.1 Some basic graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.4.2 Paths and other trees . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.4.3 Graphs formed from cliques . . . . . . . . . . . . . . . . . . . . . . . 46 3.4.4 Class Null graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.4.5 Strongly chordal graphs . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.5 Sums and products of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 50 vii 3.5.1 Disjoint unions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.5.2 Cartesian products . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.5.3 Strong direct products . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.5.4 Categorical products . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.6 Fractional isomorphisms and equitable partitions . . . . . . . . . . . . . . . 57 3.7 Mycielski graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.8 Miscellaneous graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.9 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4 Minimum Fractional Total Dominating Functions and Maximum Frac- tional Open Packing Functions 67 4.1 Functions which are both minimum fractional total dominating and maxi- mum fractional open packing . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.2 De?nition of the classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.3 The principle of complementary slackness . . . . . . . . . . . . . . . . . . . 69 4.4 A partial classi?cation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.4.1 Class Null? graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.4.2 Regular graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.4.3 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.4.4 Partial trampolines and generalized Haj?os graphs . . . . . . . . . . . 73 4.5 Sums and products of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.5.1 Disjoint unions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.5.2 Cartesian Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.6 Fractional isomorphisms and equitable partitions . . . . . . . . . . . . . . . 76 4.7 The Mycielski construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.8 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5 Domination Null and Packing Null Vertices 81 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.2 Absence of Domination Null and Packing Null Vertices . . . . . . . . . . . . 82 5.3 Total Domination Null and Open Packing Null Vertices . . . . . . . . . . . 83 5.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6 Roman Domination 85 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.2 Roman domination as an integer program . . . . . . . . . . . . . . . . . . . 86 6.2.1 Beamers and bu?ers . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.3 Closed neighborhood fractional Roman domination . . . . . . . . . . . . . . 90 6.3.1 Closed neighborhood beamers and bu?ers . . . . . . . . . . . . . . . 91 6.4 Fractional isomorphisms revisited . . . . . . . . . . . . . . . . . . . . . . . . 93 6.5 Legion mobilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.5.1 Bounds on ?R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 viii 7 Open Problems 102 7.1 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 7.1.1 Open problems from Chapter 2 . . . . . . . . . . . . . . . . . . . . . 102 7.1.2 Open problems from Chapter 3 . . . . . . . . . . . . . . . . . . . . . 102 7.1.3 Open problems from Chapter 4 . . . . . . . . . . . . . . . . . . . . . 102 7.1.4 Open problems from Chapter 5 . . . . . . . . . . . . . . . . . . . . . 103 7.1.5 Open problems from Chapter 6 . . . . . . . . . . . . . . . . . . . . . 103 7.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Bibliography 104 Appendix A: Notation 115 Appendix B: Non?Invariants of Fractional Isomorphisms 119 Appendix C: Classification of Graphs With 5 or Fewer Vertices 125 ix List of Figures 1.1 A solution to the facilities location problem for C5, using 2 bases (180 troops). 1 1.2 A fractional solution of the facilites location problem for C5, using 5 bases (150 troops). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 A labeled graph and its adjacency matrix. . . . . . . . . . . . . . . . . . . 3 1.4 Dominating sets of queens on a standard chessboard. . . . . . . . . . . . . 5 1.5 (a) A minimum dominating function, (b) an MFDF, (c) an MFPF, and (d) a maximum packing of C5 with a chord. . . . . . . . . . . . . . . . . . . . 7 1.6 (a) A minimum total dominating function, (b) an MTFDF, (c) an MFOPF, and (d) a maximum open packing of C5 with a chord. . . . . . . . . . . . . 9 1.7 Graph products: the (a) Cartesian product P4squareP5, (b) categorical product P4 ?P5, (c) strong direct product P4 ?P5, and (d) disjoint union P4 ?P5. 14 1.8 (a) The corona K3 ?K1 and (b) the corona K1 ?K3. . . . . . . . . . . . . 16 1.9 Y (P2) and Y (Y (P2)) = Y (C5). . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.10 (a) The trampoline on 12 vertices T(K6) and (b) the partial trampoline T(P2squareP3). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.11 (a) The generalized Haj?os graph [K5] and (b) the partial generalized Haj?os graph [C5]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1 Two di?erent drawings of the Petersen graph. . . . . . . . . . . . . . . . . 19 2.2 Fractionally isomorphic graphs. . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3 Two fractionally isomorphic non-regular graphs. . . . . . . . . . . . . . . . 22 2.4 A coarsest equitable partition. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.5 Fractionally isomorphic connected graphs. . . . . . . . . . . . . . . . . . . . 28 x 2.6 Non-fractionally isomorphic graphs with the same degree sequence and graph spectra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.7 Fractionally isomorphic Cartesian products. . . . . . . . . . . . . . . . . . 32 2.8 Fractionally isomorphic non-Hamiltonian and Hamiltonian graphs. . . . . . 36 2.9 Graphs on ?ve or less vertices with the same degree sequence. . . . . . . . 37 2.10 Links. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.1 (a) A dominating packing function, (b) a fractional dominating packing func- tion, and (c) a minimum fractional dominating function which is not a pack- ing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2 The ?ve classes as di?erent intersections of the sets DG (in yellow) and PG (in blue); with DG ?PG in green. . . . . . . . . . . . . . . . . . . . . . . . 40 3.3 (a) A healthy spider: K?1,6 and (b) a wounded spider. . . . . . . . . . . . . 45 3.4 A collection of disjoint cliques each connected to a central vertex. . . . . . 46 3.5 (a) An MFDF (non-packing), (b) an MFPF (non-dominating), and (c) an FDPF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.6 Unique solutions to Nx = 1. . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.7 The Lattice of Classes, with the join operator: Class (G) ? Class (H) = Class (G?H). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.8 A neighborhood partition of V (P2squareP9). . . . . . . . . . . . . . . . . . . . . 52 3.9 (a) An MFPF which is non?dominating and (b) an FDPF of P4squareP4. . . . . 54 3.10 The categorical products P3 ?P3 ? Class P and P3 ?P4 ? Class N. . . . 56 3.11 G and H are fractionally isomorphic, with G ? Class D, thus H ? Class D. 58 3.12 Y (K1 ?????K1) and Y (P4). . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.13 (a) A Pancyclic graph, (b) The Moser spindle, (c) A 3-cube with a vertex removed, (d) A wounded spider, (e) A Tree on 6 vertices, (f) A tree on 7 vertices, (g) G3,3 minus a vertex of degree two. . . . . . . . . . . . . . . . . 63 3.14 The Herschel graph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.15 Graphs needed to complete the classi?cation of graphs with 5 or fewer ver- tices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 xi 4.1 (a) The black vertices form a maximum open packing and a minimum total dominating set, (b) its characteristic function, an FTD-OPF; and (c) an FTD-OPF of C4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.2 The ?ve classes as di?erent intersections of the sets D?G (in light gray) and P?G (in dark gray); with D?G ?P?G in gray. . . . . . . . . . . . . . . . . . . . 68 4.3 An MFOPF which is not total dominating of a double star. . . . . . . . . . 73 4.4 (a) An FTD-OPF and (b) an MFOPF which is not total dominating of the partial trampoline T(C6). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.5 (a) An MFTDF which is not an open packing and (b) an MFOPF which is not total dominating of the generalized Haj?os graph, [K5]. . . . . . . . . . . 75 4.6 Three fractionally isomorphic Class D? graphs. . . . . . . . . . . . . . . . . 78 5.1 Domination null vertices (gray), and packing null vertices (red) of [G47]. . 81 5.2 Packing null vertices (red) of P4. . . . . . . . . . . . . . . . . . . . . . . . . 82 6.1 The Roman Empire. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.2 A Roman graph G. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 6.3 Mobilize some of the legions of an MRDF to obtain a total dominating set. 97 6.4 Mobilize some of the legions of an MRDF to obtain a total dominating set. 98 6.5 (a) The legions form a MRDF and (b) the red vertices form a minimum double dominating set of the partial generalized Haj?os graph [C5] . . . . . 98 1 Size of automorphism groups. . . . . . . . . . . . . . . . . . . . . . . . . . 119 2 Independent sets of maximum size. . . . . . . . . . . . . . . . . . . . . . . 119 3 Minimum proper colorings. . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 4 Minimum proper edge colorings. . . . . . . . . . . . . . . . . . . . . . . . . 120 5 Largest induced cliques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 6 Maximum matchings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 7 C6 and C3 ?C3 drawn with minimum number of edge crossings in the plane. 121 8 Fractional chromatic number, fractional clique number, and fractional inde- pendence number. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 xii 9 Minimum dominating sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 10 Minimum total dominating sets. . . . . . . . . . . . . . . . . . . . . . . . . 122 11 Minimum restrained dominating sets. . . . . . . . . . . . . . . . . . . . . . 122 12 Minimum 2-dominating sets. . . . . . . . . . . . . . . . . . . . . . . . . . . 122 13 Minimum double dominating sets. . . . . . . . . . . . . . . . . . . . . . . . 123 14 Minimum Roman dominating functions. . . . . . . . . . . . . . . . . . . . 123 15 Maximum minimal dominating sets. . . . . . . . . . . . . . . . . . . . . . . 123 16 E?cient domination number. . . . . . . . . . . . . . . . . . . . . . . . . . . 124 17 Maximum 2?packings (closed neighborhood packings). . . . . . . . . . . . 124 18 Maximum open neighborhood packings. . . . . . . . . . . . . . . . . . . . . 124 19 Class N graphs on 5 or fewer vertices. . . . . . . . . . . . . . . . . . . . . 125 20 Class I graphs on 5 or fewer vertices. . . . . . . . . . . . . . . . . . . . . . 125 21 Class D graphs on 5 or fewer vertices. . . . . . . . . . . . . . . . . . . . . . 125 22 Class P graphs on 5 or fewer vertices. . . . . . . . . . . . . . . . . . . . . . 126 23 Class E graphs on 5 or fewer vertices. . . . . . . . . . . . . . . . . . . . . . 127 xiii Chapter 1 Introduction to Domination, Fractional Graph Theory, and Linear Programming 1.1 Introduction Consider the following facilities location problem, where we are trying to ?nd the best locations of, for example, military bases, with the property that each base can handle threats at its location and any neighboring location. We say that a set of locations is a solution to the facilities location problem if threats can be handled at each location (for each location, either there is a base at this location or there is a neighboring location with a base). Suppose also that handling a threat at any location requires 90 troops. See Figure 1.1. 90 troops 90 troops Figure 1.1: A solution to the facilities location problem for C5, using 2 bases (180 troops). Instead of having each station manned with 90 troops, we can spread those resources out over the locations. If additional bases do not cost much to build, then we may be able to save money (at least in the long run) by building more bases and relaxing the resource requirement at each base. Figure 1.2 gives a fractional solution to the problem above, using only 150 troops, with the same ability to handle a threat at any location. In this solution, 1 we have a base at each location, but each has 1/3 of the resources. One can check that if there were a threat at any location, there would be enough resources from its base and the two neighboring bases to handle the threat. We call this solution optimal since there is no solution using less resources. 30 troops 30 troops 30 troops 30 troops 30 troops Figure 1.2: A fractional solution of the facilites location problem for C5, using 5 bases (150 troops). 1.2 Definitions A graph G = (V,E) consists of a set V (G) of vertices (sometimes called nodes) and a set E(G) of edges which are two-subsets of V . Elements of E, {u,v} are denoted as uv. Let G = (V,E) be a simple ?nite graph of order |V| = n, without loops or multiple edges. Two distinct vertices u and v are said to be adjacent if uv ? E(G). The degree of a vertex v ? V (G), denoted by dG(v), is the number of vertices v is adjacent to. When the graph is clear from context, we write d(v) instead. We denote the number of edges in a graph |E| by ?. The maximum degree of a graph G, denoted by ?(G), is the maximum value of dG(v) taken over all vertices v ? V (G). The minimum degree is denoted by ?(G). In notation and terminology, we try to follow [94], [95], [30] and [157]; for instance, Cn is the cycle on n vertices and Pn is the path on n vertices. As notation is not yet standard in Graph Theory, a complete list of notation used in this dissertation, can be found in Appendix A. 2 A graph can be completely determined by its vertex set and the knowledge of which pairs of vertices are adjacent. This same information can be stored in a matrix. If we order the vertices of the graph G by {v1,...,vn}, the adjacency matrix (with respect to this ordering) is the n ? n matrix A(G) = [ai,j] where aij = 1 if vi is adjacent to vj in G and 0 otherwise. The (closed) neighborhood matrix, denoted by N(G), is de?ned by N(G) = A(G) + I, where I is the n by n identity matrix. When the graph is clear from context, we write A and N for the adjacency matrix and neighborhood matrix respectively. adj v1 v5 v6 v2v7 v3 A = ? ?? ?? ?? ?? ?? ? 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 1 1 1 0 0 1 0 ? ?? ?? ?? ?? ?? ? v4 Figure 1.3: A labeled graph and its adjacency matrix. There are other matrices which store the information from a graph. The vertex-edge incidence matrix is a n ? ? matrix B with bi,j = 1 if vertex vi is incident with the edge ej and 0 otherwise. If we keep the ordering of the vertices of the graph G in Figure 1.3 and then order the edges as E = {v1v2,v2v3,v3v4,v4v5,v5v6,v6v7,v1v7,v1v4,v4v6,v6v2,v2v5, v2v6,v3v6,v3v5,v5v1}, then we can form its vertex-edge incidence matrix B displayed below. B = ? ?? ?? ?? ?? ? 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 ? ?? ?? ?? ?? ? 3 Given a graph G and a subset of vertices S ? V (G), the induced subgraph H = G[S] is the graph formed using the vertices in S, and whenever two of these vertices are adjacent in G, they are adjacent in H. The open neighborhood of a vertex v ? V (G) is de?ned as NG(V ) = {u ? V|uv ? E}, the set of all vertices adjacent to v. Note that dG(v) = |NG(v)| for all v ? V (G). The closed neighborhood of a vertex v ? V (G) is de?ned as NG[v] = {v}? NG(v). We denote the open and closed neighborhood respectively as N(v) and N[v] when the graph G is clear from context. For a set S ? V , let N(S) = uniontextu?S N(u) and let N[S] = uniontextu?S N[u]. 1.2.1 Domination and variations on domination We say that a vertex ?dominates? itself and all of its neighbors. A set of vertices S ? V is called a dominating set i? every vertex v ? V is either an element of S or is adjacent to some element of S. That is, a set of vertices S ? V is dominating i? N[S] = V . Domination began as a problem on a chessboard, when a question was posed in [118] as to the minimum number of queen pieces that can be placed on a chessboard so that every square is either occupied by a queen, or can be occupied by one of the queens in a single move. It was conjectured that the solution would consist of 5 queens and became known as the ?Five Queens problem?. We present two well-known solutions, depicted in Figure 1.4(a) and (b). Solution (a) to the ?ve queens problem also has the property that no two queens can attack each other in a single move, thus this solution is an independent dominating set. Solution (b) to the ?ve queens problem also has the property that any two queens can attack each other in a single move. When a vertex is unable to dominate itself, we have a variation of domination, intro- duced by Cockayne, Dawes and Hedetniemi [39]. A set of vertices S ? V is called a total dominating set i? every vertex v ? V is adjacent to some element of S. That is, a set of vertices S ? V is total dominating i? N(S) = V . The size of the smallest such set is the 4 (a) (b) Figure 1.4: Dominating sets of queens on a standard chessboard. total domination number, denoted as ?t. If G has vertices of degree 0, called isolates, then no such set exists. As observed in [85], another way to de?ne a total dominating set is a dominating set for which the induced subgraph, G[S], contains no isolates. In a dominating set, every vertex in V is dominated at least once. If we require that every vertex be dominated at least twice, we have a double dominating set ([85]). The size of a smallest such set is denoted as dd(G) (or as ??2(G)). If we think of our vertices in our dominating set S as computer servers, in communi- cation with vertices (or computers) in V ? S, then what happens if one server fails? To protect the network, we can have every vertex in V ?S be dominated twice, that is, every v ? V ?S is adjacent to at least two distinct vertices in S. The size of the smallest such 2-dominating set is denoted as ?2. This is di?erent than a double dominating set, since members of S need not be dominated twice. The generalization of 2-domination is called k-domination ([94]); in which S is dominating and every v ? V ?S is adjacent to at least k distinct members of S. The size of the smallest such k-dominating set is denoted as ?k. 5 1.2.2 Let?s get fuzzy! Fractional graph theory has its roots in coloring, starting with independent results from [109], [159], and [38], where the fractional chromatic number was explored. Fractional domination was ?rst de?ned in [60] and [102]. A dominating function on a graph G is a function g : V ? {0,1} such that g(N[v]) = summationtext u?N[v] g(u) ? 1 for all vertices v ? V . The characteristic function ?S de?ned by ?S(v) = 1 when v ? S and 0 otherwise is a dominating function i? S is a dominating set. A minimum dominating function on a graph G, naturally enough, is a dominating function g which attains the minimum value of |g| = summationtextv?V g(v). This minimum is denoted by ?(G) and called the domination number of G. Every function ? : V ? [0,1] has a vector representation vector? = (?(v1),...,?(vn))T for any ?xed ordering v1,...,vn of the vertices of G. Throughout this dissertation, we shall often refer to a function and its vector interchangeably. In the following, we represent a vector vectorx by x. Two vectors satisfy x > y if and only if xi > yi for all i. Likewise, x < y if and only if xi < yi for all i; x ? y and x ? y are de?ned similarly. For any function g : V (G) ? A ? R, we call the value g(v) ? A the weight of the vertex. We will often de?ne functions by assignments of weights. We call |g| the total weight of the function. When g is de?ned by its vector g, the weight of any vertex vi ? V is the ith coordinate of the vector g (for some ?xed ordering of the vertices). The vector f of any dominating function f satis?es the constraint Nf ? 1. A function g : V ? [0,1] whose vector satis?es this inequality shall be called a fractional dominating function, henceforth FDF. A minimum fractional dominating function (MFDF) is an FDF g such that the value |g| = summationtextv?V g(v) is as small as possible. This minimum value is the fractional domination number of G, denoted by ?f(G). 6 A set S ? V is called a (closed) neighborhood packing if for any vertex x ? G, |S ? N[x]| ? 1. This set is sometimes referred to as a 2-packing, since for all u,v ? S the distance from u to v is at least 3. A function h : V ? {0,1} is called a packing function if it is the characteristic function of some neighborhood packing. Note that any packing function f satis?es the matrix inequality Nf ? 1. A maximum packing function on a graph G is a packing function h which attains the maximum value of |h| = summationtextv?V h(v), denoted by ?(G) and called the packing number of G (the packing number is the same as the 2-packing number, P2(G)). A function h : V ? [0,1] is a fractional packing function (FPF) provided that h(N[v]) ? 1 for all v ? V . Just as for integer packing functions, the vector h of any such FPF h satis?es the constraint Nh ? 1. A maximum fractional packing function (MFPF) is an FPF h such that the value attained by |h| = summationtextv?V h(v) is as large as possible. This maximum is the fractional (closed neighborhood) packing number of G and is denoted by ?f(G). (a) (d)(c)(b) 1 2 0 0 0 0 0 0 0 1 1 1 16 13 0 0 01212 1 2 1 2 Figure 1.5: (a) A minimum dominating function, (b) an MFDF, (c) an MFPF, and (d) a maximum packing of C5 with a chord. Bange, Barkhauskas, and Slater ([6]) called f an efficient dominating function, if f(N[v]) = 1 for every v ? V . It is possible for some graphs to have no e?cient domi- nating function (as with the graph in Figure 1.5). This lead to the de?nition of the e?cient domination number (see [164]). We start with a maximal packing S (not necessarily maxi- mum), and look at how much domination gets done, |N[S]|. The maximum value of |N[S]|, 7 taken over all maximal packings S, is called the efficient domination number, denoted as F(G). If a graph G has an e?cient dominating function, then F(G) = n, since there is a packing which is also dominating. If no such function exists, then F(G) < n. Alternatively, we can de?ne the e?cient domination number as the maximum value of summationtextn i=1 (1 + d(vi))gi, taken over all packing functions g. From this we can de?ne the efficient fractional domination number as the maximum value of summationtextni=1 (1 + d(vi))gi, taken over all (maximal) FPFs g. This maximum value is denoted by Ff(G). If a graph G has an e?cient fractional dominating function, then Ff(G) = n, since there is a fractional packing which is also fractional dominating. If no such function exists, then Ff(G) < n. A total dominating function on a graph G without isolates is a function g : V ? {0,1} such that g(N(v)) = summationtextu?N(v) g(u) ? 1 for all vertices v ? V . The characteristic function ?S de?ned by ?S(v) = 1 when v ? S and 0 otherwise is a total dominating function i? S is a total dominating set. A minimum total dominating function on a graph G is a total dominating function g which attains the minimum value of |g| = summationtextv?V g(v). This minimum is denoted by ?t(G) and called the total domination number of G. If G has isolates, then we say ?t = ?. In [157] and [67], the authors use ? for this parameter; however, we will reserve this notation for the upper domination number, the size of a largest minimal dominating set. The vector f of any total dominating function f satis?es the constraint Af ? 1. A function g : V ? [0,1] whose vector satis?es this inequality shall be called a fractional total dominating function, henceforth FTDF. A minimum fractional total dominating function (MFTDF) is an FTDF g such that the value |g| = summationtextv?V g(v) is as small as possible. This minimum value is the fractional total domination number of G, denoted by ??f(G). A set S ? V is called an open neighborhood packing if for any vertex x ? G, |S?N(x)| ? 1. A function h : V ? {0,1} is called an open packing function if it is the function of some neighborhood packing. Note that any packing function f satis?es the matrix inequality 8 Af ? 1, where f represents the vector of f. A maximum open packing function on a graph G is an open packing function h which attains the maximum value of |h| = summationtextv?V h(v), denoted by ?t(G) and called the open packing number of G. A function h : V ? [0,1] is a fractional open packing function (FOPF) provided that h(N(v)) ? 1 for all v ? V . Just as for integer open packing functions, the vector h of any such FOPF h satis?es the constraint Ah ? 1. A maximum fractional open packing function (MFOPF) is an FOPF h such that the value attained by |h| = summationtextv?V h(v) is as large as possible. This maximum is the fractional open (neighborhood) packing number of G and is denoted by ??f(G). (a) (d)(c)(b) 0 1 0 1 0 1 2 0 0 0 0 0 13 13 1 1 1 2 2 3 1 2 1 2 2 3 Figure 1.6: (a) A minimum total dominating function, (b) an MTFDF, (c) an MFOPF, and (d) a maximum open packing of C5 with a chord. A set of edges M ? E(G) is called a matching if no two edges in M are incident. The matching number ? is the size of a maximum matching. A function g : E ? [0,1] is a fractional matching function provided that for each vertex v ? V , summationtextuv?E g(uv) ? 1. The fractional matching number ?f is the maximum of summationtexte?E g(e) = |g| taken over all fractional matching functions on G. If we restrict the values of g(e) to be only 0 or 1, then g is the characteristic function of a matching. A function g : E ? {0,1} is a matching function provided that for each vertex v ? V , summationtextuv?E g(uv) ? 1. Here we have that the matching number is the largest value of summationtext e?E g(e) = |g| taken over all matching functions f on G. 9 1.3 Integer and linear programming A linear program is an optimization problem where we are maximizing or minimizing a function subject to some constraints. Let M be a real k by m matrix and b, c, x, and y be real column vectors of the appropriate sizes. For our purposes, linear programs (or LPs) can be expressed in the following two forms: maximize cTx subject to Mx ? b, x ? 0 (1.1) minimize bTy subject to MTy ? c, y ? 0 (1.2) The linear program in (1.2) is called the (linear programming) dual of the linear program in (1.1). The expression cTx in (1.1) is called the objective function and any vector x satisfying the constraints Mx ? b, x ? 0 is called a feasible solution. The maximum (respectively minimum) value of the objective function taken over all feasible solutions is called the ?value? of the LP. Any feasible solution to the LP on which the objective function attains the value is called an optimal solution. If we require, in addition, that the optimal solutions be integer valued, then the above two linear programs are called integer programs (or IPs). When we start with an integer program and then remove or drop the constraint that the optimal solutions need to be integer valued, we obtain the linear relaxation of the IP. We now state a few fundamental theorems from linear programming. Theorem 1.3.1 ([69] Strong Duality Theorem) A linear program and its dual have the same value. A very important result from the theory of linear programming gives a condition which the optimal vectors of an LP and its linear dual must obey (we do not have a source for the original proof). 10 Theorem 1.3.2 ([141] Principle of complementary slackness) Let x? be any optimal solution to the linear program: maximize cTx subject to Mx ? b, x ? 0, and let y? be any optimal solution to the dual linear program: minimize bTy subject to MTy ? c, y ? 0. Then: x? ? (MTy? ?c) = y? ? (Mx? ?b) = 0. Many problems in graph theory can be formulated as integer programs. In fractional graph theory, many fractional parameters can be de?ned by the value of a relaxed linear program. If the matrix and vectors of an LP all have rational entries, then the value will be rational, hence, the reason the term ?fractional? instead of real in (1.4) ([141]). The problem of determining the domination number can be formulated as an integer program using the neighborhood matrix N; ?(G) is the value of the integer program: minimize 1Ty subject to: Ny ? 1, y ? 0, yi ?Z+ (1.3) From this, we can de?ne fractional domination number as the value of the linear program- ming relaxation of the above integer program (1.3); ?f is the value of the linear program: minimize 1Ty subject to: Ny ? 1, y ? 0 (1.4) Determining ?f(G) can be likewise formulated in LP terms: maximize 1Tx subject to: Nx ? 1, x ? 0 (1.5) Each of the LP?s (1.4), (1.5) is the other?s dual linear problem, since N is a symmetric matrix; therefore, ?f(G) = ?f(G) for all graphs G. Determining the packing number can be formulated in IP terms, by adding the additional constraint to (1.5) that the optimal 11 solution needs to be integer valued; ?(G) is the value of the integer program: maximize 1Tx subject to: Nx ? 1, x ? 0, xi ?Z+ (1.6) By the theory of linear relaxations, ?(G) ? ?f(G) and ?f(G) ? ?(G). The problem of determining the total domination number can be formulated as an integer program using the adjacency matrix A; ?t(G) is the value of the integer program: minimize 1Ty subject to: Ay ? 1, y ? 0, yi ?Z+ (1.7) From this, we can de?ne fractional total domination number as the value of the linear programming relaxation of the above integer program (1.7); ??f is the value of the linear program: minimize 1Ty subject to: Ay ? 1, y ? 0 (1.8) Determining ??f(G) can be likewise formulated in LP terms: maximize 1Tx subject to: Ax ? 1, x ? 0 (1.9) Each of the LP?s (1.8), (1.9) is the other?s dual linear problem, since A is a symmetric matrix; therefore, ??f(G) = ??f(G) for all graphs G. Determining the packing number can be formulated in IP terms, by adding the additional constraint to (1.9) that the optimal solution needs to be integer valued; ?t(G) is the value of the integer program: maximize 1Tx subject to: Nx ? 1, x ? 0, xi ?Z+ (1.10) By the theory of linear relaxations, ?t(G) ? ??f(G) and ??f(G) ? ?t(G). 12 Putting these inequalities and equalities together we get the well-known string of in- equalities for all graphs G ?(G) ? ?f(G) = ?f(G) ? ?(G) (1.11) ?t(G) ? ??f(G) = ??f(G) ? ?t(G) (1.12) As proved in [157], equality holds in (1.11) for strongly chordal graphs (see section 3.4.5 for a de?nition) and equality holds in (1.12) for chordal bipartite graphs. Given a graph G, the problem of ?nding the e?cient domination number F(G) can be formulated as in IP (see [164]), where di = d(vi): maximize (d + 1)Tx subject to Nx ? 1, x ? 0, xi ?Z+ (1.13) Relax (1.13) to obtain the LP formulation of e?cient fractional domination. Ff is the value of the LP: maximize (d + 1)Tx subject to Nx ? 1, x ? 0 (1.14) An alternative LP formulation of e?cient fractional domination: maximize 1TNx subject to Nx ? 1, x ? 0 (1.15) The problem of ?nding the fractional matching number can be formulated as a linear program, where B is the vertex-edge incidence matrix of G (with respect to some ?xed ordering of the vertices and edges); ?f(G) is the value of the linear program: maximize 1Tx subject to Bx? 1, x ? 0 (1.16) 13 1.4 New graphs from old As in many areas of mathematics, such as group theory, new objects are often obtained from old by considering sums and products. 1.4.1 Graph sums and products (b) P4 ?P5 (d) P4 ?P5(c) P4 ?P5 (a) P4squareP5 Figure 1.7: Graph products: the (a) Cartesian product P4squareP5, (b) categorical product P4 ?P5, (c) strong direct product P4 ?P5, and (d) disjoint union P4 ?P5. The Cartesian product of G and H is denoted by GsquareH; the vertices are the ordered pairs {(x,y)|x ? V (G),y ? V (H)}, and two vertices (u,v) and (x,y) are adjacent if and only if one of the following is true: u = x and v is adjacent to y in H; or v = y and u is 14 adjacent to x in G. When G is the path on m vertices and H is the path on n vertices, GsquareH is called the m by n grid graph, denoted as Gm,n. The categorical product of G and H is denoted by G?H. The vertices are the ordered pairs {(x,y)|x ? V (G),y ? V (H)}, and two distinct vertices (u,v) and (x,y) are adjacent if and only if u ? NG(x) and v ? NH(y). This product has been called many other names in the literature (often with di?erent notation as well), like conjunctive product, weak direct product, direct product, cardinal product, or even just product. The strong direct product of G and H is denoted by G?H. The vertices are the ordered pairs {(x,y)|x ? V (G),y ? V (H)}, and two distinct vertices (u,v) and (x,y) are adjacent if and only if u ? NG[x] and v ? NH[y]. Next we look at a graph sum. The disjoint union of graphs G and H, denoted by G?H, is de?ned by the vertex and edge sets V = V (G) ?V (H) and E = E(G) ?E(H), where V (G) ?V (H) = ?. 1.4.2 Graph constructions There are also several ways to get new graphs from old, such as taking the complement of a graph, taking the line graph, etc. In Chapter 3, we will investigate a well-known graph construction, called the Mycielski construction. In [68], Frucht and Harary de?ne the corona of two graphs G and H as the graph G?H formed from one copy of G and |V (G)| copies of H where the ith vertex of G is adjacent to every vertex in the ith copy of H (see Figure 1.8). Given a graph G with vertices {v1,...,vn}, Mycielski (in [139]) constructed a new graph Y (G) with vertices {x1,...,xn}?{y1,...,yn}?{z}. Whenever vjvk is an edge in G, each of xjxk, xjyk and xkyj are edges in Y (G). Finally, each of the zyi are edges in Y (G). (See [130], [139] and [157]). This construction is primarily investigated in graph colorings; however, there has been at least one paper on fractional domination which uses 15 (b)(a) Figure 1.8: (a) The corona K3 ?K1 and (b) the corona K1 ?K3. the construction, [67]. We call the sequence of graphs Y0 = P2,Y1 = Y (P2), Y2 = Y (Y (P2)), ...,Yk = Y k(P2) the Mycielski graphs. Y (G) Y (G) GG Figure 1.9: Y (P2) and Y (Y (P2)) = Y (C5). Motivated by [157] and [22], we de?ne a trampoline T(Kn) on 2n vertices (n ? 3) as fol- lows: begin with a complete graph on the vertices {v1,...,vn}, add the vertices {u1,...,un} and add the edges uivi and uivi+1 (with vn+1 = v1); see Figure 1.10a. Trampolines are re- ferred to as n-suns in [22]. A partial trampoline TH(G) is the graph on 2n vertices formed from any Hamiltonian graph G with Hamilton cycle H = v1v2...vn. This can be thought of as taking a trampoline and removing edges from ?inside? the Kn (see see Figure 1.10b). When there is only one Hamiltonian cycle, the H will be omitted. As in [8], the generalized Haj?os graph is the graph [Kn] on n +parenleftbign2parenrightbig vertices formed by starting with a clique on three or more vertices, then adding a vertex uij for each pair of vertices vi,vj in Kn add the edges uijvi and uijvj (see see Figure 1.11a). As with partial 16 (b)(a) Figure 1.10: (a) The trampoline on 12 vertices T(K6) and (b) the partial trampoline T(P2squareP3). trampolines we can start with any Hamiltonian graph G on three or more vertices and then apply the construction on G to obtain the partial generalized Haj?os graph [G] with n +parenleftbign2parenrightbig vertices (see Figure 1.11b). (b)(a) Figure 1.11: (a) The generalized Haj?os graph [K5] and (b) the partial generalized Haj?os graph [C5]. 17 1.5 Notes Upper and lower bounds on the fractional domination number were found indepen- dently in [54] and [80]. For any graph on n vertices, n?(G)+1 ? ?f(G) ? n?(G)+1. In [52], equality in vizing-like conjectures were found to hold: ?f(G?H) = ?f(G)?f(H) and ??f (G?H) = ??f(G)??f(H). In [28], Chang found an upper bound for the domination num- ber of the m?n grid graph (for m and n at least 8): ? (Gm,n) ? ceilingleftBig(m+2)(n+2) 5 ceilingrightBig ?4. In [33], it was conjectured that equality holds in the above upper bound for su?ciently large m and n. In [89], Hare found bounds for ?f(Gm,n) for m,n > 2 involving the Fibonacci numbers. There are many other products which can be investigated; see [114] for 256 di?erent graph products. There are many other variations on domination, which we do not discuss (for an excel- lent exposition on this topic see [94]). We do investigate a recent variation on domination in Chapter 6 called Roman domination. In this dissertation we only consider a vertex to dominate vertices which are at most distance one away. There is a large area of research where vertices in S can dominate vertices which are distance at most k away from it, called distance-k domination. If vertices are allowed to dominate with di?erent distances, then we have broadcast domination (see [13] and [113]). In our IP formulations, we ?rst relaxed to its LP, took the dual, then un-relaxed to form the ?linear dual? IP. In [24], Bul?n noted, that it is incorrect to speak of the dual of an IP. There exist several IPs which are dual to a given IP. For instance, we could take the Lagrangian dual or the surragate dual of the domination IP (1.3) (see [141]). 18 Chapter 2 Fractional Isomorphisms 2.1 Isomorphisms of graphs As in any area of mathematics, it is important to know when two objects are the ?same? or ?di?erent?. The numbers 3 and 62 are equal though they are not identical in form; the groups A3 and Z3 are isomorphic though not identical. So when are two possibly di?erently drawn graphs the ?same?? If two graphs di?er from one another only by the way they are drawn or by the way their vertices (or edges) are labeled, we say they are isomorphic. To be more precise, a graph G is isomorphic to H, denoted G ?= H, if there exists a one-to-one mapping ? (called an isomorphism) from V (G) onto V (H) such that ? preserves adjacency and non?adjacency; that is, uv ? E(G) i? ?(u)?(v) ? E(H). Figure 2.1: Two di?erent drawings of the Petersen graph. Let G and H be two graphs with adjacency matrices A and B respectively. A permu- tation matrix is a {0,1} matrix with exactly one 1 in each row and column. G and H are isomorphic if and only if there exists a permutation matrix P such that P?1AP = B. This permutation matrix acts on the the columns and the rows of A, in a sense relabeling the 19 vertices of G to make H. An equivalent de?nition of isomorphic graphs is the existence of a permutation matrix P which satis?es AP = PB. 2.2 Fractional Isomorphisms of Graphs The requirement that P is a permutation matrix can be restated as: P is a matrix such that (where 1 is the n? 1 matrix of all ones): (1) P1 = 1 (2) 1TP = 1 (3) pi,j ? {0,1} Relaxing condition (3), the requirement that P be a {0,1} matrix, amounts to requiring the entries only be nonnegative; however we still want P1 = 1 and 1TP = 1. Condition (1) gives rise to the use of a row stochastic matrix, a non-negative matrix whose row sums are all 1. Condition (2) gives rise to the use of a column stochastic matrix, which is the transpose of a row stochastic matrix. A n?n row stochastic matrix B, which has the property that BT is also row stochastic, is said to be doubly stochastic. Thus, a doubly stochastic matrix S is a matrix whose entries are nonnegative, and whose rows and columns all sum to one; that is S1 = 1 and ST1 = 1 (see [111]). Note that S must have non-negative entries, and hence each entry must be in the interval [0,1]. Let G and H be two graphs with adjacency matrices A and B respectively. We say G and H are fractionally isomorphic if and only if there exists a doubly stochastic matrix S so that AS = SB; we denote this relationship by G ?=f H. The doubly stochastic matrix S may depend on which adjacency matrices A and B are used, which in turn depend on which orderings of the vertices of G and H are used. It is easy to see, however, that if G and H are fractionally isomorphic with respect to one choice of adjacency matrices, then they 20 are fractionally isomorphic with respect to any other choice of adjacency matrices: suppose AS = SB, P and Q are permutation matrices so that A? = PTAP and B? = QTBQ; then A = PA?PT and B = QB?QT. So PA?PTS = SQB?QT or A?(PTSQ) = (PTSQ)B?. Further, PTSQ is doubly stochastic. v6 v2 v4 H u2 u3 u1 u6 u5 u4v5 v3 G v1 Figure 2.2: Fractionally isomorphic graphs. As an example, let A be the adjacency matrix of the G = 6-cycle and B be the adjacency matrix of H the disjoint union of two 3-cycles (with respect to the orderings in Figure 2.2). The doubly stochastic matrix S = 16J6 (where J6 is the 6 ? 6 matrix of all ones) satis?es AS = SB. Thus G and H are fractionally isomorphic; and we write C6 ?=f C3 ?C3. Note that these two graphs are both 2-regular. In [146], it was proved by taking S = 1nJn that any two k-regular graphs on n vertices are fractionally isomorphic. Theorem 2.2.1 ([146]) If G and H are both regular graphs of degree k on n vertices, then G ?=f H. For a non-regular example, consider the two graphs in Figure 2.3. If we let A be the adjacency matrix of G and let B be the adjacency matrix of H (both with respect to the given ordering of V ), then the doubly stochastic matrix S = 12J2 ? 14J4 satis?es AS = SB. Thus, G and H are fractionally isomorphic. 21 u2v1 v3 v6 v4v5 u3 u6 u5u4 H v2 u1 G Figure 2.3: Two fractionally isomorphic non-regular graphs. 2 66 66 66 66 66 66 4 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 0 3 77 77 77 77 77 77 5 2 66 66 66 66 66 66 4 1 2 1 2 0 0 0 0 1 2 1 2 0 0 0 0 0 0 14 14 14 14 0 0 14 14 14 14 0 0 14 14 14 14 0 0 14 14 14 14 3 77 77 77 77 77 77 5 = 2 66 66 66 66 66 66 4 1 2 1 2 0 0 0 0 1 2 1 2 0 0 0 0 0 0 14 14 14 14 0 0 14 14 14 14 0 0 14 14 14 14 0 0 14 14 14 14 3 77 77 77 77 77 77 5 2 66 66 66 66 66 66 4 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 0 0 3 77 77 77 77 77 77 5 Just as the relation of being isomorphic is an equivalence relation on the set of all unlabeled graphs, and thus di?erently drawn versions of the same graph are in the same equivalence class, so it is with fractional isomorphism. Lemma 2.2.2 ?=f is an equivalence relation. Proof. In the following, let A, B, and C be adjacency matrices of the graphs G, H, and K, respectively. ? Re?exivity: let S = In which trivially satis?es AS = SA, thus G ?=f G. ? Symmetry: suppose G ?=f H, then there exists a doubly stochastic matrix S which satis?es AS = SB. Then take the transpose of both sides to get STA = BST. Since ST is doubly stochastic, H ?=f G. 22 ? Transitivity: suppose G ?=f H and H ?=f K. There exist doubly stochastic matrices S and T so that AS = SB and BT = TC. Then consider A(ST) = (AS)T = (SB)T = S(BT) = S(TC) = (ST)C. Since the product of any two doubly stochastic matrices is doubly stochastic, G ?=f K. square Thus the relation of being fractionally isomorphic is an equivalence relation on the set of all unlabeled graphs. So it is natural to wonder what is di?erent or the same about any two fractionally isomorphic graphs. We look at the many di?erences in the next section. Regular graphs, speci?cally n?cycles and disjoint unions of smaller cycles, will play a crucial role in providing examples. 2.3 Non-invariants of fractional isomorphisms A parameter ? is called invariant if ?(G) = ?(H) whenever G and H are fractionally isomorphic. A parameter ? is called non?invariant if ?(G) negationslash= ?(H) for two fractionally isomorphic graphs G and H. The terminology comes from isomorphism invariants, which are parameters and properties which do not depend on which labeling of the vertices is used. For example, the adjacency matrix is not invariant (with respect to graph isomorphism). As we will see, fractionally isomorphic graphs can be quite di?erent (just look at 3- regular graphs on 50 vertices). A list of some non?invariant parameters is given in Appendix B. A list of some properties which can be di?erent is given in Theorem 2.3.5. First we give some necessary conditions for a graph parameter to be invariant (with respect to fractional isomorphism). Let G be a graph with connected components C1,...,Cj. We say that a parameter ? is additive if ?(G) = ?(C1) + ??? + ?(Cj); multiplicative if ?(G) = ?(C1)?(C2)????(Cj); or superlative if ?(G) = max{?(C1),...,?(Cj)} or ?(G) = min{?(C1),...,?(Cj)}. In the 23 following, as with the corona de?nition, ?k copies of G? refers to the disjoint union of G with itself k times, i.e. kG = ?ki=1G = G?????Gbracehtipupleft bracehtipdownrightbracehtipdownleft bracehtipupright k . Lemma 2.3.1 Every cycle Cn is fractionally isomorphic to the disjoint union of a1 copies of C3, a2 copies of C4 and a3 copies of C5, for some non-negative integers a1, a2, and a3. Proof. For any n ? 3, there exist integers ai ? 0 so that n = 3a1 +4a2 +5a3. Both Cn and a1C3?a2C4?a3C5 are regular of degree two on n vertices, and thus fractionally isomorphic. square Theorem 2.3.2 If ? is an additive invariant parameter, then ?(Cn) = nk, for some con- stant k, where k is an integer if ? is an integer valued parameter. Proof. Let ?(C3) = 3k. Then since C60 ?=f 20C3 ?=f 15C4 ?=f 12C5, it follows from additivity that 12?(C5) = 15?(C4) = 20?(C3), and so ?(C4) = 43?(C3) = 4k; and ?(C5) = 5 3?(C3) = 5k. Additivity then requires that ?(Cn) = nk. square The following is a consequence of Theorem 2.3.2: Corollary 2.3.3 If ? is a multiplicative invariant parameter, then |?(Cn)| = rn, for some constant r. Proof. Let ? = log|?|. Then ? is an additive parameter, which by Theorem 2.3.2 must take the value kn on Cn for some constant k. So ?(Cn) = 10?(Cn) = 10nk = rn, where r = 10k. square Theorem 2.3.4 If ? is a superlative invariant parameter, then for any m and n, ?(Cn) = ?(Cm). Proof. Assume that ? is maximized over the connected components of a graph; the proof for a minimizing parameter is similar. Since C60 ?=f 20C3 ?=f 15C4 ?=f 12C5, we have that 24 ?(C60) = max{?(C3)} = max{?(C4)} = max{?(C5)}, and hence ?(C3) = ?(C4) = ?(C5). By Lemma 2.3.1, for any m and n, ?(Cn) = max{?(C3),?(C4),?(C5)} = ?(Cm). square The following superlative graph parameters are non?invariant: vertex independence number, clique number, chromatic number, edge chromatic number, matching number, and girth. The fractional chromatic number is also non-invariant, since ?f(C2m+1) = 2 + 1m which would, of course, be di?erent for cycles of di?erent order. The fractional clique num- ber, ?f, turns out to be equal to the fractional chromatic number for all graphs by linear programming strong duality, and thus, ?f is trivially also non-invariant. The following ad- ditive graph parameters are non?invariant: domination number, total domination number, 2-domination number, double domination number, restrained domination number, indepen- dent domination number, e?cient domination number, packing number, open neighborhood packing number, Roman domination number (see Chapter 6), and the maximum size of a minimal dominating set. The parameter |Aut(G)| is non-invariant. This parameter is almost multiplicative; if no two components of G are isomorphic, then |Aut(G)| = producttextH |Aut(H)|, where the product is taken over the components of G. The crossing number of a graph ?(G) is the fewest number of edge crossings taken over all drawings of G in the plane (the minimum can be taken over what is called ?good? drawings of G, see [70]). This parameter is non?invariant, since ?(C6) = 0 negationslash= 1 = ?(C3 ?C3) (see Figure 7 in Appendix B). According to [157], ?f(G) = ?f( ?G), and thus with Theorem 2.6.3, ?f, the fractional independence number, is also non-invariant. See Figures 1-18 in Appendix B, where we give examples for each non-invariant parameter mentioned above. We are unsure of the parameters such as fractional irredundance, but conjecture that this is invariant. In an attempt to describe everything which can be di?erent given two 25 arbitrary fractionally isomorphic graphs, we also investigate which properties are non? invariant. ? is an eigenvalue of a matrix A, if Ax = ?x for some nonzero vector x. Eigenvalues can be computed by factoring the determinant of A?It. The multiset of eigenvalues of a matrix M is denoted by ?(M). The non-increasing sequence of n eigenvalues of an adjacency matrix A of a graph G of order n is called the spectrum of the graph, and is denoted by Spec(G) (see [87]). The eigenvalue of A of maximum absolute value is called the spectral radius, denoted by ?G. Theorem 2.3.5 The following are non?invariant: ? spectrum ? maximum eigenvalue of the Laplacian ? Hamiltonicity ? vertex transitivity ? chordality Proof. Let A and B be adjacency matrices of G = C6 and H = C3 ? C3 (both with respect to the orderings used in Figure 2.2). Their spectra are di?erent, since Spec(G) = {2,1,1,?1,?1,?2}, whereas Spec(H) = {2,2,?1,?1,?1,?1}. We will see later that although their spectra may be di?erent, they necessarily share the maximum eigenvalue, in this case, 2. Although the spectral radius of the adjacency matrices of any two fractionally isomorphic graphs are the same (see Theorem 2.5.1), the result does not necessarily hold of the Laplacian matrices of any two fractionally isomorphic graphs. The Laplacian of a graph G is the matrix L = D ? A, where D is the diagonal matrix of degrees (Di,i = d(vi) and Di,j = 0 whenever i negationslash= j). ?(L(G)) = {4,3,3,1,1,0}, whereas, ?(L(H)) = {3,3,3,3,0,0}. 26 ?L(G) = 4, whereas ?L(H) = 3. C6 is Hamiltonian, yet the disjoint union of two 3?cycles, C3 ?C3 is non?Hamiltonian (see also Figure 2.8 for two connected examples). For vertex? transitivity, see C7 which is vertex transitive and C3 ?C4 which is not. For chordality, C6 is not chordal, whereas C3 ?C3 is chordal. A = ? ?? ?? ?? ? 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 ? ?? ?? ?? ? B = ? ?? ?? ?? ? 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 ? ?? ?? ?? ? square 2.4 Equitable partitions Before we can discuss what fractionally isomorphic graphs have in common, we need to de?ne a class of special partitions of the vertices (see [75]). We denote the number of edges from a vertex v to a set S of vertices by d(v,S),. A partition of the vertex set V into disjoint sets V1,...,Vr is equitable if for any vertices x,y ? Vi, d(x,Vj) = d(y,Vj) for all possible choices of i and j. Thus, the induced subgraph G[Vi] is regular for all i, and the bipartite subgraph G[Vi,Vj] made from only the edges between Vi and Vj is bi-regular (the vertex degrees within each part are equal) for all i negationslash= j. If P and Q are equitable partitions of a common set S, P is called a refinement of Q, provided every cell of P is contained in a cell of Q. When P is a re?nement of Q, we say that Q is coarser than P. Two vertices u and v are in the same orbit if there exists an automorphism ? of the graph such that ?(u) = v. Although choosing the cells to be orbits under automorphisms yields an equitable partition, for some graphs there exist coarser equitable partitions. Consider the graph in Figure 2.4, the equitable partition {{v1,v2,v3,v4},{v5,v6,v7,v8}} on the left is coarser than the equitable partition formed by the orbits {{v1,v2},{v3,v4},{v5,v6,v7,v8}}. Note that v1 and v3 are not in the same orbit 27 C1 v1 v4 v5 v3v8 v7v2 v6 v1 v2 v3 v4 v5 v6 v7 v8 C2 Figure 2.4: A coarsest equitable partition. since there is no automorphism which would send v1 to v3 (v1 is in a 3?cycle, while v3 is not). Every graph has a unique coarsest equitable partition (see [157]). We shall de?ne the cell-adjacency matrix A(C) for an equitable partition C as follows: the rows and columns of A(C) shall be indexed by the cells of C. The entry A(C)i,j will be equal to d(x,Vj) for any x ? Vi. We say that graphs G and H have a common equitable G H Figure 2.5: Fractionally isomorphic connected graphs. partition C if they have the same sizes of cells and A(C) is identical to B(C) (with respect to the same ordering of C). For the equitable partition Q = {red,white} of V (G) and V (H) in Figure 2.5, the cell adjacency matrices (with respect to the ordering: red, white) are the 2 ? 2 matrices: 28 A(Q) = ? ? 2 2 1 2 ? ? B(Q) = ? ? 2 2 1 2 ? ? 2.5 What is the same about fractionally isomorphic graphs? We begin by stating invariant parameters and properties proven in [146]. These serve as necessary conditions for two graphs to be fractionally isomorphic. Theorem 2.5.1 ([146]) The following are fractional isomorphism invariants. ? n = |V| ? ? = |E| ? degree sequences ? spectral radius HG Figure 2.6: Non-fractionally isomorphic graphs with the same degree sequence and graph spectra. The above necessary conditions for fractionally isomorphic graphs are not su?cient. Figure 2.6, due to Allen Schwenk (see [157]), depicts two graphs with the same degree sequences (thus the same number of vertices and edges), and spectra; yet they are not fractionally isomorphic. This is due to a result in [146]: if G is a graph and F is a forest 29 and if G ?=f F then G ?= F (this is based on a result in McKay?s Masters Thesis and article [136]: the only equitable partitions of a forest are those arising from orbits). The main theorem from [146] states necessary and su?cient conditions for two graphs to be fractionally isomorphic. We refer the reader to [157] for the de?nition of D?, the matrix of iterated degree sequences. Theorem 2.5.2 ([146]) The following are equivalent: ? G ?=f H ? G and H have a common coarsest equitable partition ? G and H have some common equitable partition ? D*(G)=D*(H) 2.5.1 An entire class of invariant fractional parameters If two graphs G and H (with adjacency matrices A and B, respectively) are fractionally isomorphic, then the following in?nite class of parameters are invariant: Theorem 2.5.3 The value of any linear program of the form: maximize cTx subject to: Mx ? b, x ? 0 (where b and c are constant vectors and M is any polynomial in A), is invariant. Proof. Suppose that G and H are fractionally isomorphic graphs. Let A and B be adja- cency matrices of G and H, respectively, and let S be a doubly stochastic matrix such that AS = SB. Let M1 = p(A) and M2 = p(B), where p(x) is a polynomial, and let ?(G) and ?(H) be the values of the linear programs (2.1) and (2.2), respectively. We aim to show that ?(G) = ?(H). max cTx subject to: M1x ? b,x ? 0 (2.1) 30 max cTx subject to: M2x ? b,x ? 0 (2.2) Suppose we can show that multiplication by S maps feasible solutions of (2.2) into feasible solutions of (2.1). It will then follow, since BST = STA, that multiplication by ST maps feasible solutions of (2.1) into feasible solutions of (2.2). Also, because c is a constant vector, and S is column stochastic, c(Sx) = (cS)x = cTx, for any vector x ? 0. It then follows that ?(G) ? ?(H). But then the equality ?(H) ? ?(G) follows as well, by the same argument with S replaced by ST, and thus ?(G) = ?(H). Suppose that x ? 0 satis?es M1x ? b. Then Sx ? 0 and M1(Sx) = p(A)Sx = S(p(B)x) = S(M2x) ? Sb = b, since b is constant and S is doubly stochastic. square Thus any fractional parameter ?f which is the value of its associated LP (satisfying the above constraints) is invariant. Note that not all fractional parameters have an associated LP where M is a polynomial in A and b, c are constant; the LP (1.16) for fractional matching uses the vertex?edge incidence matrix. In fact, it is a consequence of Theorem 2.5.3 that no non-invariant parameter can possibly have an LP formulation as in that theorem. Two parameters whose LPs do satisfy Theorem 2.5.3 are fractional domination (1.4) and fractional total domination (1.8). Corollary 2.5.4 ?f and ??f are invariant parameters. Proof. Both parameters are the value of a linear program, where the matrix is a polynomial in A, namely A + I and A respectively. The vectors b and c are the constant vector 1 in both LP?s. square 2.6 Graph products We wonder how fractional isomorphisms interact with graph products. We call a graph product, ?, preserving if G ?=f G? and H ?=f H? implies G?H ?=f G? ?H?. 31 Theorem 2.6.1 square, ?, and ? are each preserving products. Proof. Suppose G ?=f G? and H ?=f H?. Then G and G? share a coarsest equitable partition A, as do H and H? (call this B). Let ? represent the graph product: square, ?, or ?. Take the equitable partition of the product G?H by taking the partition A of V (G) and repeating it for each copy of V (G). Then replace G with G? in G?H, which does not alter the equitable partition of G ? H, to obtain G ? H ?=f G? ? H. Next, take the equitable partition of the product G? ?H by taking the partition B of V (H) and repeating it for each copy of V (H). Then replace H with H? in G? ? H, which does not alter the equitable partition of G? ? H, to obtain G? ? H ?=f G? ? H?. Do both replacements simultaneously (or at the same time) to obtain G?H ?=f G? ?H?. square Although the corona is not technically a graph product, Conjecture 2.6.2 If G ?=f G? and H ?=f H? then G?H ?=f G??H? and H?G ?=f H??G?. Figure 2.7: Fractionally isomorphic Cartesian products. This together with Corollary 2.5.4, gives us a way to compute the fractional domi- nation and fractional total domination numbers of very large prisms. For example, since P3squareC60 ?=f 20(P3squareC3), ?f(P3squareC60) = 20?f(P3squareC3) = 20157 and we have ??f(P3squareC60) = 20??f(P3squareC3) = 20(3). Note also since P3squareC60 ?=f 20(P3squareC3) ?=f 15(P3squareC4) ?=f 12(P3squareC5), ?f(P3squareC60) = 20157 = 15207 = 12257 = 3007 . Let m ? 3 be any positive integer, with m = 3a+4b+5c. Then we obtain the following formulas for the fractional domination and fractional total domination numbers of PnsquareCm 32 (in the case of n = 2, the graph is regular): ?f(P2squareCm) = m2 ?f(P3squareCm) = a157 + b207 + c257 = 5m7 ?f(P4squareCm) = a3011 + b4011 + c5011 = 10m11 ?f(P5squareCm) = a6018 + b8018 + c10018 = 10m9 ?f(P6squareCm) = a11429 + b15229 + c19029 = 38m29 ?f(P7squareCm) = a21347 + b28447 + c35547 = 71m47 ?f(P8squareCm) = a19538 + b13019 + c32538 = 65m38 ??f(P2squareCm) = 2m3 ??f(P3squareCm) = a(3) + b(4) + c(5) = m ??f(P4squareCm) = a185 + b245 + c(6) = 6m5 ??f(P5squareCm) = a92 + b(6) + c152 = 3m2 ??f(P6squareCm) = a367 + b487 + c607 = 12m7 ??f(P7squareCm) = a(6) + b(8) + c(10) = 2m ??f(P8squareCm) = a203 + b809 + c1009 = 20m9 Since ?f(G?H) = ?f(G)?f(H), there is no need to use the above technique to compute the fractional domination number of very large strong direct products. However, we can 33 use Theorem 2.6.1 compute the fractional total domination numbers of large strong direct products. 2.6.1 Constructions We want to know which constructions are preserved by fractional isomorphisms. We call a graph construction T preserving if G ?=f G? implies T (G) ?=f T (G?). Theorem 2.6.3 If G ?=f H, then ?G ?=f ?H. Proof. Fix an ordering of the vertices and let A and B be adjacency matrices of G and H respectively (with respect to the ?xed ordering). There exists a doubly stochastic matrix S satisfying AS = SB. Let J be the n ? n matrix of all ones, then J ? I ? A is the adjaceny matrix of the complement ?G and J ?I ?B is the adjaceny matrix of complement ?H. Since S commutes with J and the identity, we have (J ?I ?A)S = JS ?IS ?AS = SJ ?SI ?SB = S(J ?I ?B). Thus ?G and ?H are fractionally isomorphic. square The Mycielski construction Y (G) de?ned in Chapter 1, turns out to be a preserving construction. Theorem 2.6.4 If G ?=f H, then Y (G) ?=f Y (H). Proof. Let A and B be adjacency matrices of G and H, respectively. As in [20], the adjacency matrix of Y (G) can be written as a 2n + 1 ? 2n + 1 block matrix as follows: ? ?? ?? A A 0 A 0n?n 1 0T 1T 0 ? ?? ?? There exists S, doubly stochastic, so that AS = SB; and we have 34 ? ?? ?? A A 0 A 0n?n 1 0T 1T 0 ? ?? ?? ? ?? ?? S 0 0 0 S 0 0T 0T 1 ? ?? ?? = ? ?? ?? S 0 0 0 S 0 0T 0T 1 ? ?? ?? ? ?? ?? B B 0 B 0n?n 1 0T 1T 0 ? ?? ?? square In [67], Fisher found that the construction u(G) = Y ( ?G) worked well with fractional domination. Corollary 2.6.5 If G ?=f H, then u(G) ?=f u(H) Proof. Suppose G ?=f H, then ?G ?=f ?H by Theorem 2.6.3. Theorem 2.6.4 then gives Y ( ?G) ?=f Y ( ?H). One more application of Theorem 2.6.3 gives the result. square 2.7 Notes For a good text on matrix theory including properties and theorems on doubly stochas- tic matrices, see [111] and [112]. The original work in this chapter was joint work with Walsh [177]. We list several open problems on this topic in Chapter 7. Most of the counterexamples for non?invariant parameters listed in Appendix B are disconnected. So what if we want to know what is the same or di?erent about any two connected fractionally isomorphic graphs. Do any of the non?invariant parameters suddenly become invariant? Ullman (in [174]) noted that the family of 3?regular graphs should still provide counterexamples for each non-invariant parameter (except those dealing with connectivity). For Hamiltonicity, we look to the Petersen graph, which is non-Hamiltonian and 3?regular on 10 vertices. The Tutte Wheel is a 3?regular graph on 10 vertices formed from a 10?cycle with ?ve added maximum diameter chords (see Figure 2.8). If two fractionally isomorphic graphs are connected and if G is Eulerian, then so is H, since degree sequences are preserved. Although, two fractionally isomorphic connected 35 Figure 2.8: Fractionally isomorphic non-Hamiltonian and Hamiltonian graphs. graphs may not have the same number of duplicated edges required for a minimum Euler- ization (see Figure 2.5). Are the graphs C6 and C3 ?C3 the smallest example of two non?isomorphic yet frac- tionally isomorphic graphs? One can check that no two non?isomorphic graphs of order n ? 4 have the same degree sequence. If there are two non?isomorphic, fractionally iso- morphic graphs of order n < 6, they are among the graphs in Figure 2.9. It turns out that our search for a smaller example fails since none of graphs in Figure 2.9 are pairwise fractionally isomorphic. Since trees are only fractionally isomorphic to themselves, the two graphs G26 and G31 cannot be fractionally isomorphic. G36 and G37 do not share the coarsest equitable partition. Lastly, ?f(G43) = 32, whereas ?f(G44) = 75. The above relaxation of the concept of isomorphism can also be applied to automor- phism. Let G be a graph with adjacency matrix A; a doubly stochastic matrix S is a fractional automorphism of G i? AS = SA. [74] discusses the history of fractional auto- morphisms (though not by that name) and some of their algebraic properties; [119] and [120] explore the connection between fractional automorphisms and fractional domination. There are also other relaxations of isomorphism. If we only require P in the isomor- phism equation P?1AP = B to be a non-singular matrix, then the graphs G and H are co-spectral (see [146]). Another relaxation of isomorphism is semi-isomorphism. Two graphs 36 G37G31 G26 G44 G43G36 {1,1,2,2,2} {2,2,2,3,3} {2,2,2,3,3} {1,2,2,2,3} {1,2,2,2,3}{1,1,2,2,2} Figure 2.9: Graphs on ?ve or less vertices with the same degree sequence. are semi-isomorphic (and write G ?=? H) if there exists two doubly stochastic matrices P and Q so that A = QBP. In [81] Grone suggested the use of ortho-stochastic matrices, which are a subclass of doubly stochastic matrices. Any matrix formed by taking the Hadamard product of a unitary matrix with its conjugate is an ortho-stochastic matrix (see [112]). Recall that two graphs G and H are isomorphic if there exists a one-to-one mapping ? from V (G) onto V (H) such that ? preserves adjacency and non?adjacency; that is, uv ? E(G) i? ?(u)?(v) ? E(H). So for two isomorphic graphs there is a one-to-one correspondence with the vertices of G and H. This one-to-one correspondence can be represented as ?links? from V (G) to V (H). In the case of fractional isomorphism, this is a bit di?erent. In [146] and [157], an equivalent de?nition of fractional isomorphism using links is given. In the ?gure below, G and H are the graphs in Figure 2.3, the links are represented by dashed lines with the weights of 14 for the red links, and 12 for the blue links. The weights come from the doubly stochastic matrix which satis?es AS = SB. 37 v6 v5 G H v1 u3v3 u5 u4 u2 u1 u6 v2 v4 Figure 2.10: Links. 38 Chapter 3 Minimum Fractional Dominating Functions and Maximum Fractional Packing Functions 3.1 Functions which are both minimum fractional dominating and maximum fractional packing In Chapter 1, we saw that ?nding minimum fractional dominating functions and maxi- mum fractional packing functions are dual linear programs. This is a very special dual pair of LPs, though, since the vectors being optimized in both problems can be interpreted as real-valued functions on the set of vertices. Hence, it becomes possible to have a function whose vector simultaneously solves both the fractional domination LP and its dual. We call a function which is both a minimum FDF and a maximum FPF a fractional dominating- packing function (FDPF). A function which is both an FDF and FPF is necessarily an MFDF and an MFPF and is therefore an FDPF. We might also refer to such an object as a (closed neighborhood) fractional partition on the vertices of G, as it forms a real-valued analogue of a partition of the vertex set of G into closed neighborhoods. 340 1 1 0 13 1313 131 3 130 0 34 140 014 Figure 3.1: (a) A dominating packing function, (b) a fractional dominating packing function, and (c) a minimum fractional dominating function which is not a packing. 39 3.2 Definition of the classes We wish to investigate the interactions of MFPFs and MFDFs. Our goal is to classify those graphs in which all MFPFs are FDPFs, or all MFDFs are FDPFs, or when there are no FDPFs at all, as well as any graphs in between. To do this we de?ne the following ?ve classes based on the intersections of the two following sets: Let DG be the set of all MFDFs on G and let PG be the set of all MFPFs on G. Every ?nite simple graph G belongs to exactly one of the classes below: ? G ? Class N (Null) if DG ?PG = ?. ? G ? Class I (Intersection) if DG ?PG negationslash= ?, DG notsubseteql PG and PG notsubseteql DG. ? G ? Class P (Packing) if DG subsetnoteql PG. ? G ? Class D (Dominating) if PG subsetnoteql DG. ? G ? Class E (Equal) if DG = PG. DG PG DG PG DGPG DG ?PG Class DClass P DG ?PG Class N Class I Class E DG ?PG DG ?PG Figure 3.2: The ?ve classes as di?erent intersections of the sets DG (in yellow) and PG (in blue); with DG ?PG in green. 40 3.3 The principle of complementary slackness The principal tool that we shall use in our investigations is the Principle of Comple- mentary Slackness, an important result in the duality theory of linear programming (see Theorem 1.3.2). Recall the neigborhood matrix, N = A + I. Proposition 3.3.1 (Applied principle of complementary slackness) Let x? be an MFPF, that is any optimal solution to the linear program: maximize 1Tx subject to Nx ? 1, x ? 0, and let y? be an MFDF, that is any optimal solution to the dual linear program: minimize 1Ty subject to NTy ? 1, y ? 0. Then x? ? (NTy? ?1) = y? ? (Nx? ?1) = 0. We give the two main consequences below: Corollary 3.3.2 If f is an MFDF and v ? V (G) for which f(v) > 0, then for any MFPF g, g(N[v]) = 1. Corollary 3.3.3 If g is an MFPF and v ? V (G) for which g(v) > 0, then for any MFDF f, f(N[v]) = 1. These corollaries, in turn, su?ce to establish a number of technical lemmas, which we now state and prove. Lemma 3.3.4 If f is an MFDF with f(v) > 0 for every vertex v ? V, then every MFPF is an MFDF, and thus PG ? DG. Proof. Let f be an MFDF on G with f(v) > 0 for each vertex v. Then by Corollary 3.3.2, every MFPF g has the property that g(N[v]) = 1 for every vertex v. So g is an MFDF. square 41 Lemma 3.3.5 If we can find two functions f and g where f is an MFDF on G with f(v) > 0 for each vertex v, and where g is an MFDF on G which is not an FPF, then G ? Class D. Proof. The MFDF f gives us PG ? DG and the MFDF (non-packing) g gives us PG subsetnoteql DG. square Lemma 3.3.6 If f is an MFPF with f(v) > 0 for each vertex v ? V, then every MFDF is an MFPF, and thus DG ? PG. Proof. Let g be an MFPF on G with g(v) > 0 for each vertex v. Then by Corollary 3.3.3, every MFDF f has the property that f(N[v]) = 1 for every vertex v. So f is an MFPF. square Lemma 3.3.7 If we can find two functions f and g where f is an MFPF on G with f(v) > 0 for each vertex v, and where g is an MFPF on G which is not dominating, then G ? Class P. Proof. The MFPF f gives us DG ? PG and the MFPF (non-dominating) g gives us DG subsetnoteql PG. square The results of Lemmas 3.3.5 and 3.3.7 also work if there is a single function which satisfy both properties of f and g simultaneously (or at the same time). This single function can be obtained by taking an appropriate convex combination of the two functions. If we can ?nd a function which is both an MFDF and an MFPF which has positive weights on each vertex, then combining Lemmas 3.3.4 and 3.3.6 yields: Corollary 3.3.8 For a graph G, if there exists an FDPF f with f(v) > 0 for each vertex v ? V, then G ? Class E. 42 3.4 A partial classification With these preliminaries in place, we are ready to begin sorting families of graphs into our ?ve classes. 3.4.1 Some basic graphs Theorem 3.4.1 Every regular graph is Class E. Proof. Let G be k-regular; then the function f(v) = 1k+1 for all v ? V is an FDPF. Since f is nonzero at each vertex, Corollary 3.3.8 tells us that G ? Class E. square Theorem 3.4.2 If ?(G) = n? 1 and G negationslash= Kn then G ? Class P. Proof. Let S be the set of vertices of maximum degree n?1. Since ? = ? = 1, the constant function f(v) = 1n is an MFPF. Since f(N[v]) < 1 for any v ? V ?S, f is not dominating. Note that V ?S is non-empty since G negationslash= Kn. Thus, by Lemma 3.3.7, G ? Class P. square It would be nice if we could determine the class of the graph by induced subgraphs. From the above two theorems, we can see this does not work. The star K1,2 is Class P and K2 is an induced subgraph, however, K2 is regular and thus Class E. Theorem 3.4.3 Let G be the complete r-partite graph with parts of size n1,n2,...,nr, r ? 2 and each nj ? 2. Then G ? Class E. Proof. As shown in [80] the function which assigns to each vertex in the jth part the positive weight of 1 (nj ? 1) parenleftBigg rsummationdisplay i=1 1 ni ? 1 + r ? 1 parenrightBigg is an FDPF. square 43 3.4.2 Paths and other trees Theorem 3.4.4 Let Pn be the path on n vertices for n ? 3. Then: Pn ? ? ??? ??? ?? ??? ??? ?? Class P, n ? 0 mod 3 Class D, n ? 1 mod 3 Class I, n ? 2 mod 3 Proof. Let vi represent the ith vertex of the path on n vertices. For any positive integer k ? 1, it is easy to check that ?(P3k) = ?(P3k) = k and ?(P3k+i) = ?(P3k+i) = k + 1 for i = 1,2. In the following cases, the bracketed blocks of weights are repeated k? 1 times. Case 1: n = 3k. Let f be the function which assigns the weight of 13 to each vertex. Since f(N[v1]) = 23, f is not dominating. So by Lemma 3.3.7, we have P3k ? Class P. Case 2: n = 3k + 1. The function f = (12, 12,[13, 13, 13],..., 12, 12)T is an MFDF with positive weights on every vertex. Since f(N[v2]) = 43, f is not packing. Therefore P3k+1 ? Class D by Lemma 3.3.5. Case 3: n = 3k + 2. The function f = (12, 12,0, 12,[12,0, 12],..., 12)T is an FDPF. The function g = (0,1,0,1,[0,0,1],...,0)T is an MFDF which is not packing (since g(N[v3]) = 2). Lastly, the function h = (1,[0,0,1],...,0,0,0,1)T is an MFPF which is not dominating (since h(N[v3k]) = 0). Therefore P3k+2 ? Class I. square Trees in general do not seem as easy to classify; however, certain classes of trees lend themselves easily to analysis. For instance, [40] and [94] de?ne a healthy spider K?1,t as the result of subdividing each edge of a star K1,t into a path of length 3 (see Figure 3.3). Exempting one or more (but not all) of the edges from this subdivision results in a wounded spider (see Figure 3.6a). In both of these classes of graphs, the vertex of degree t is referred to as the head vertex, and those of degree one the foot vertices. 44 (b)(a) Figure 3.3: (a) A healthy spider: K?1,6 and (b) a wounded spider. Theorem 3.4.5 K?1,t ? Class I Proof. The function which assigns the weight of 0 to the head vertex, t?1t to the foot vertices, and 1t otherwise, is an FDPF. The function which assigns 1 to the foot vertices and 0 otherwise is an MFPF which is not dominating. Lastly, the function which assigns 1 to the vertices of degree two and 0 otherwise, is an MFDF which is not packing. Therefore, G ? Class I. square Note that for the healthy spider obtained from subdividing both edges of a K1,2 we get P5 which was already shown to be in Class I by the preceding theorem. The next theorem was stated and proved by Walsh in [153]. Theorem 3.4.6 Suppose that T is a tree and T ? Class E. Then |V (T)| ? 2. Proof. Suppose that T is a Class E tree with at least three vertices; then we can ?nd two adjacent vertices x,y such that d(x) = 1 and d(y) > 1. Let f be an FDPF; then f(N[x]) = f(x) +f(y) = 1. We shall de?ne two more functions, fx and fy, which are equal to f everywhere except on N[x]; we set fx(x) = 1 and fx(y) = 0; likewise, fy(x) = 0 and fy(y) = 1. Clearly fx is an MFPF and fy is an MFDF, but at least one of them is not a FDPF. square 45 adj Kn2 vq v3v1 c Knq Kn3 v2 Kn1 Figure 3.4: A collection of disjoint cliques each connected to a central vertex. 3.4.3 Graphs formed from cliques If we take a ?nite collection of q > 1 disjoint cliques {Kn1,...,Knq} and for each clique designate a vertex vi to be adjacent to a vertex c outside of each clique, then we have a graph on summationtextni + 1 vertices. We call c the central vertex, each of the vertices in the Kni which are not adjacent to the central vertex peripheral vertices, and the {vi} juncture vertices. The central vertex has degree q, the peripheral vertices have degrees ni, and the juncture vertices have degrees ni + 1. Theorem 3.4.7 Let G be constructed from a collection of q > 1 disjoint cliques as above. If ni ? 2 for all i, then G ? Class I. Proof. Clearly ? = ? = q, so the function which assigns the weight of 1 to each of the juncture vertices and 0 otherwise is an MFDF which is non-packing. The function which assigns the weight of 1 to a single peripheral vertex in each clique and 0 otherwise is an MFPF which is non-dominating. Lastly, take the previous MFPF and move the weight of 1 from the peripheral vertex of just one clique to its juncture vertex. This is an FDPF. Therefore G ? Class I. square 46 0 0 0 0 0 0 00 1 1 1 1 0 0 0 0 (a) (c)(b) 0 00 1 1 1 1 1 1 1 1 Kn3Kn1 Kn2 Kn3 Knq Kn1 Kn2 Kn3 Knq Kn1 Kn2 Knq Figure 3.5: (a) An MFDF (non-packing), (b) an MFPF (non-dominating), and (c) an FDPF. 3.4.4 Class Null graphs Up until now we have seen examples of graphs in every class except Class N, where no MFDF is an MFPF and no MFPF is an MFDF. That is for any graph in Class N there are no FDPFs on G. Actually, in this class, it is true that no FDF is a FPF and no FPF is a FDF. There is an easy characterization of Class N graphs using neighborhood matrices. Proposition 3.4.8 G is in Class N if and only if the system Nx = 1 has no non-negative solutions. Proof. If Nx = 1 has a non-negative solution, then the vector x is an FDPF, thus G is not in Class N. Likewise, if G is not in Class N, then there exists a vector x satisfying Nx = 1, with x ? 0, that is each xi is non-negative; thus the system has a non-negative solution. square The smallest examples of graphs in Class N are a wounded spider obtained from sub- dividing one edge of a K1,3, a K3 with two pendant edges, and C5 with an added chord (depicted in Figure 3.6). In each of these graphs, the red vertex is forced to have a negative weight when solving the system Nx = 1. 47 (b) (c)(a) 1 1 ?1 ?1 111 0 0 002 ?1 0 1 Figure 3.6: Unique solutions to Nx = 1. With the above wounded spider (depicted in Figure 3.6a), upon solving Nx = 1, we ?nd the unique solution is x = (2,?1,0,1,1)T . By Proposition 3.4.8, the above wounded spider is in Class N. The next Class N graph is K3 with two pendant edges (depicted in Figure 3.6b). Upon solving Nx = 1, we ?nd the unique solution is the function x which assigns a weight of ?1 to the vertex of degree two, 1 to each vertex of degree three and 0 to each vertex of degree one. By Proposition 3.4.8, K3 with two pendant edges is in Class N. The last Class N graph on ?ve vertices is C5 with a chord (see Figure 3.6c). Upon solving Nx = 1, we ?nd the unique solution is x = (?1,1,0,0,1)T . By Proposition 3.4.8, this graph is Class N. In [121], we describe all MFDFs of this graph, f = (0, 12,t, 12 ?t, 12)T where 0 ? t ? 12. The unique MFPF is g = (12,0, 12, 12,0)T . It should be noted that x = (?1,1,0,0,1)T could be considered as an e?cient {?1,0,1} dominating function. However, we will restrict our attention to FDFs and FPFs, which by de?nition, only have weights from the unit interval [0,1]. We showed above (in Theorems 3.4.1 and 3.4.4) that the other four classes are in?nite. We shall now do the same for Class N using some results from [121], which we restate here using our present terminology. Lemma 3.4.9 If f is an MFDF and v ? V (G) for which f(N[v]) > 1, then every MFPF g satisfies g(v) = 0. 48 Proof. Suppose g is an MFPF with g(v) > 0. Then by Corollary 3.3.3, every MFDF f satis?es f(N[v]) = 1, a contradiction. square Lemma 3.4.10 If g is an MFPF and v ? V (G) for which g(N[v]) < 1, then every MFDF f satisfies f(v) = 0. Proof. Suppose f is an MFDF with f(v) > 0. Then by Corollary 3.3.2, every MFPF g satis?es g(N[v]) = 1, a contradiction. square In Chapter 1, we de?ned two graph constructions, the trampoline and the general- ized Haj?os graph. These constructions are de?ned for G = Kn, n ? 3. We also de?ned corresponding partial constructions with Kn replaced by any Hamiltonian graph G. Theorem 3.4.11 Let G be Hamiltonian, then T(G) is Class N. Proof. As noted in [121], the function f de?ned by f(ui) = 12 and f(vi) = 0 (for all i) is an FPF; the function g de?ned by g(vi) = 12 and g(ui) = 0 (for all i) is an FDF. Since |f| = |g|, f is a maximum FPF and g is a minimum FDF. Since f(N[ui]) < 1 for each ui, then by Lemma 3.4.10, every MFDF h satis?es h(ui) = 0. Since g(N[vi]) = 32 > 1 for each vi, then by Lemma 3.4.9, every MFPF k satis?es k(vi) = 0. Therefore, no MFPF can be an MFDF. square Note that the above proof does not depend on which Hamiltonian cycle H is chosen in the construction, hence, the H in TH(G) is omitted. Corollary 3.4.12 All trampolines are in Class N. Theorem 3.4.13 For any Hamiltonian graph G, the partial generalized Haj?os graph [G] is Class N. 49 Proof. The function f(uij) = 1n?1 (for all 1 ? i < j ? n) and 0 otherwise is an MFPF. The function g(vi) = 12 (for all i) and 0 otherwise is an MFDF. Since f(N[uij]) < 1 for each uij, then by Lemma 3.4.10, every MFDF h satis?es h(uij) = 0. Since g(N[vi]) ? 32 > 1 for each vi, then by Lemma 3.4.9, every MFPF k satis?es k(vi) = 0. Therefore, no MFPF can be an MFDF. square 3.4.5 Strongly chordal graphs A well studied class of graphs for which equality holds in (1.11) is the class of strongly chordal graphs. A graph is strongly chordal if any cycle on four or more vertices contains a chord and there are no induced trampolines. One might anticipate that if G is a strongly chordal graph, then ?nding which class G is in would be an easy problem, especially since there are a fair number of papers on strongly chordal graphs in the literature. However, ?nding which class a strongly chordal graph belongs to is not an easy problem, since trees are strongly chordal and there are examples of trees in each class (see Theorems 3.4.1, 3.4.4 and Figure 3.6a). In fact, nothing can be said about the class of G if ?(G) = ?(G). 3.5 Sums and products of graphs There is an entire chapter in [95] regarding the domination number of a product of two graphs (see also [114] and [142]). It seems natural, then, to ask whether we can determine the class of a graph product in terms of its ingredients. We will brie?y examine a few graph products and disjoint unions in this section using the notation of [67] for the products and [30] for the disjoint union. Again, a complete list of notation can be found in the appendix. 3.5.1 Disjoint unions Domination and neighborhood packing (in both their integer and fractional forms) interact quite simply with disjoint unions. 50 Lemma 3.5.1 The function f : V (G ? H) ? [0,1] is a fractional dominating (packing) function on G?H if and only if f|G is dominating (packing) on G and f|H is dominating (packing) on H. Using this, we can determine the class of a disjoint union of two graphs, given the classes of the two starting graphs. The results are easy to check, and are summarized in Table 3.5.1. ? Class D Class E Class I Class N Class P Class D Class D Class D Class I Class N Class I Class E Class D Class E Class I Class N Class P Class I Class I Class I Class I Class N Class I Class N Class N Class N Class N Class N Class N Class P Class I Class P Class I Class N Class P Table 3.1: The class of the disjoint union of two graphs. Table 3.5.1 suggests a lattice structure on the classes where the lattice join operation is Class (G) ? Class (H) = Class (G ? H). To complete the de?nition of our lattice, we would need to de?ne a meet operation ? on the classes. There does exist a meet operation (Class (G) ? Class (H)) on the classes, since there are are a ?nite number of elements and there is a minimum element, Class E. We present what such a lattice of the classes should look like in Figure 3.7. 3.5.2 Cartesian products Theorem 3.5.2 Let G be the 2 by n grid graph P2squarePn. Then for n > 1 we have: P2squarePn ? ? ??? ? ???? Class E, n ? 0 mod 2 Class D, n ? 1 mod 2 51 D N I P E Figure 3.7: The Lattice of Classes, with the join operator: Class (G) ? Class (H) = Class (G?H). Proof. We consider odd and even values of n separately. Case 1: n = 2k. For k = 1 we have C4 which is regular. For k > 1 order the vertices of P2squareP2k as {v1,1,...,v1,2k;v2,1,...,v2,2k}. The function f(vi,j) = ? ??? ? ??? ? j/2 2k + 1, j ? 0 mod 2 k? ((j ? 1)/2) 2k + 1 , j ? 1 mod 2 is an FDPF which has positive weights on each vertex so P2squareP2k ? Class E by Corol- lary 3.3.8. Case 2: n = 2k + 1. For k ? 1 we can ?nd a partition of vertices into closed neighbor- hoods, that is we can ?nd k + 1 vertices p1,...,pk+1 so that each vertex of G is in precisely one closed neighborhood. The vertices pi are straightforward to ?nd; Figure 3.8 gives a de- piction of such a partitioning of V (P2squareP9) into the closed neighborhoods {N[p1],...,N[p5]}, p4p2 p1 p3 p5 Figure 3.8: A neighborhood partition of V (P2squareP9). 52 where the pi are colored black. In fact, there is a formula for ?nding the pi based on the ordering used in case 1: {p1,...,pk+1} = {v1,1,v3,2,v5,1,...}, where pk+1 is v2k+1,1 if k is even, or v2k+1,2 if k is odd. For k = 1 we have a partition using the vertices p1 and p2. The function which assigns 1 to each pi and 0 otherwise is an FDPF. Now consider the constant function which assigns the weight of 13 to each vertex; this function is an MFDF which is not packing. Therefore by Lemma 3.3.5, P2squareP3 ? Class D. For k ? 2 we have a partition using the vertices p1,pk+1 of degree two and p2,...,pk of degree three. The function which assigns 1 to each pi and 0 otherwise is an FDPF. The function which assigns the weight of 0 to each of {p2,...,pk} and 13 otherwise is an MFDF which is not packing. Taking a convex combination of these two functions we have an MFDF with positive weights on each vertex. Therefore by Lemma 3.3.5, P2squareP2k+1 ? Class D. square This result is somewhat discouraging, in that it suggests the absence of an obvious relationship between the classes of two graphs and that of their Cartesian product: the class of P2squarePn depends only on the parity of n, while the class of Pn depends on the congruence class of n (mod 3). We classify one more grid graph below. See Figure 3.9 to see that P4squareP4 = G4,4 is Class P. 3.5.3 Strong direct products An important product we consider is the strong direct product of G and H, denoted by G?H. (see Figure 1.7d). Here we are a little more fortunate. The interaction between fractional domination and strong direct products is studied in [52]; the following facts are observed there, which we state as lemmas. Lemma 3.5.3 ?f(G?H) = ?f(G)?f(H) 53 (b)(a) 1 8 1 8 1 8 1 8 4 8 4 8 1 8 2 8 4 8 1 8 2 8 4 8 2 8 1 8 1 8 2 8 1 1 1 1 Figure 3.9: (a) An MFPF which is non?dominating and (b) an FDPF of P4squareP4. Lemma 3.5.4 Let P be an m? k matrix, Q be an s ?t matrix, x and z be k-vectors, y and w be t-vectors, and ? denote the tensor product. Then: 1. (P ?Q)(x?y) = (Px) ? (Qy). 2. If x ? z ? 0 and y ? w ? 0, then x?y ? z ?w. 3. Let G and H be graphs with adjacency matrices AG and AH, respectively; then the adjacency matrix of their product AG?H is given by AG ?AH. Theorem 3.5.5 Let x1 and x2 be MFDFs on G and H, respectively. Then x? = x1 ?x2 is an MFDF on G?H. Proof. AG?Hx? = (AG ?AH)(x1 ?x2) = (AGx1) ? (AHx2) ? 1|V (G)| ?1|V(H)| = 1|V (G?H)| This shows x1 ?x2 is an FDF on G?H; x1 ?x2 is an MFDF by Lemma 3.5.3. square 54 An analogous proof gives us: Theorem 3.5.6 Let y1 and y2 be MFPFs on G and H, respectively. Then y? = y1 ?y2 is an MFPF on G?H. This shows that the properties of being dominating and packing are maintained in products; we can also show that the properties of being non-dominating and non-packing are likewise preserved. Lemma 3.5.7 If f1 and f2 are MFDFs on G and H, respectively, with at least one of f1 and f2 not packing; then f1 ?f2 is an MFDF on G?H which is not packing. Proof. From Theorem 3.5.5 we have that f1?f2 is an MFDF. Suppose f1 is not a packing. To show that f1 ?f2 is not packing, let u ? V (G) such that f1(N[u]) > 1; such a vertex must exist, since otherwise f1 would be an FPF. Since the weight of a vertex in the strong direct product equals the product of the weights on its component vertices, then by part 3 of Lemma 3.5.4, we can see that (f1 ? f2)(N[(u,w)]) = f1(N[u])f2(N[w]) > 1, and hence f1 ?f2 is not packing. square Lemma 3.5.8 If f1 and f2 are MFPFs on G and H, respectively, with at least one of f1 and f2 not dominating; then f1 ?f2 is an MFPF on G?H which is not dominating. Proof. As above, with the inequalities reversed. square Together, these give: Theorem 3.5.9 The class of G?H is determined by the table below, where the first row is the class of G and the first column is the class of H. Proof. Theorems 3.5.5 and 3.5.6 show that the tensor product of MFDFs and MFPFs are themselves MFDFs and MFPFs of the product graph, and hence if f1 and f2 are FDPFs 55 ? Class D Class E Class I Class N Class P Class D Class D Class D Class I Class N Class I Class E Class D Class E Class I Class N Class P Class I Class I Class I Class I Class N Class I Class N Class N Class N Class N Class N Class N Class P Class I Class P Class I Class N Class P Table 3.2: The class of the strong direct product of two graphs. of G and H, respectively, then f1 ? f2 is an FDPF of G?H. Further, Lemma 3.5.8 can be used to ?nd an MFPF which is not dominating if at least one of G and H is Class P or Class I. Lemma 3.5.7 can be used to ?nd an MFDF which is not packing, if at least one of G and H is Class D or Class I. Thus, if one of G and H is Class I and the other is not Class N, then G?H ? Class I. If at least one of G,H is Class N, then G?H ? Class N. The remaining cases are left to the reader. square 3.5.4 Categorical products P3?P3 can be viewed as the disjoint union of G = C4 and H = K1,4, (see Figure 3.10). C4 is Class E and K1,4 is Class P. Thus C4 ? K1,4 ?= P3 ? P3 ? Class P by Table 3.5.1. P3 ?P4 can be viewed as the disjoint union of two copies of G96 which can be shown to be Class N, thus G96 ? G96 ?= P3 ?P4 is Class N. P3 ?P4P3 ?P3 Figure 3.10: The categorical products P3 ?P3 ? Class P and P3 ?P4 ? Class N. 56 3.6 Fractional isomorphisms and equitable partitions In Chapter 2, we found that any two fractionally isomorphic graphs have the same fractional domination number. Using this, we get a new necessary condition for two graphs to be fractionally isomorphic. Theorem 3.6.1 If two graphs G and H are fractionally isomorphic, then they belong to the same class. Proof. We proceed by considering the action of the matrix S on a function f; speci?cally, we shall show that Sf has the property of being minimum fractional dominating (or maximum fractional packing) on G if f has that property on H. Suppose A and B are adjacency matrices of G and H respectively and S is a doubly stochastic matrix such that AS = SB. Suppose that f is an MFDF on H; then (B + I)f = 1 + ?, where ? ? 0. Then: N(Sf) = (NS)f = (AS + IS)f = (SB + SI)f = S((B + I)f) = S(1 + ?) = 1 + S? Since both S and ? are non-negative, so is their product. Therefore, Sf is an MFDF on G (note that Sf is minimum, since |Sf| = |f| and ?f(G) = ?f(H) as shown in Chapter 2.). Further, S? = 0 if and only if ? = 0. Hence, if f is an MFDF but not packing in H, then the same goes for Sf in G. 57 A similar demonstration will reveal that if f is a maximum fractional packing on H (and thus (B+I)f = 1?? for some nonnegative vector ?), then Sf is a maximum fractional packing on G, and likewise that the property of being non-dominating is preserved. To complete the proof, note that fractional isomorphism is an equivalence relation, and hence symmetric; speci?cally, if AS = SB, then BST = STA. Hence, S sends DH into DG, PH into PG and DH ?PH into DG ?PG. Further, ST sends DG into DH, PG into PH and DG ?PG into DH ?PH, hence the two graphs share a class. square HG Figure 3.11: G and H are fractionally isomorphic, with G ? Class D, thus H ? Class D. Although being in the same class is a necessary condition for two graphs to be frac- tionally isomorphic, it is not su?cient. Both K2,3 and C5 are in Class E, however, they are not fractionally isomorphic to each other (since their degree sequences are di?erent). Let C = {V1,...,Vr} be an equitable partition of the vertices v1,...,vn of G. De?ne the matrix S(C) by: S(C)i,j = ? ???? ??? ? 0 if vi and vj are in di?erent cells of C |Vk|?1if vi and vj are both in Vk Theorem 3.6.2 Let f be a fractional dominating (or packing) function on G. Then fC = S(C)f is a fractional dominating (packing) function on G with the property that, if vi and vj belong to the same cell of C, then fC(vi) = fC(vj). 58 Proof. First we show that S(C) is a fractional automorphism of G (with adjacency matrix A). To show that S(C)A = AS(C), it su?ces to show that either of these products is sym- metric. Consider the element (AS(C))i,j = summationtextk Ai,kS(C)k,j and its image under transposition. Let us say that vi ? Va and vj ? Vb; by the construction of the two matrices, it is clear that (AS(C))i,j = d(vi,Vb)|V b| , and similarly (AS(C))j,i = d(vj,Va)|Va| . If a = b then these two quantities are equal, since G[Va] is regular. If a negationslash= b, then we observe the two quantities to be equal from d(vi,Vb)|Va| = d(vj,Va)|Vb|; this equation results from counting the edges of the bi- partite graph G[Vi,Vj] two di?erent ways. Therefore S(C) is a fractional automorphism of G. It is proved in [120], that if S is a fractional automorphism of G and if f is a fractional dominating or packing function, then so is Sf. Thus, to complete the proof, we only need show that the product function is constant on each cell of the equitable partition. This follows from the observation that, if Vi = {vi1,...,vim}, then for any k,1 ? k ? m we have S(C)f(vik) = 1msummationtextj f(vij). square Corollary 3.6.3 Let C be an equitable partition of G. If G has an MFDF which is non- packing, an MFPF which is non-dominating, or an FDPF, then it has such a function which is constant on each cell of C. Suppose that f is a function on the vertex set of G which is constant on the cells of C, and de?ne a new function f(C) on the cells of C such that f(C)(Vi) = f(xi) for xi ? Vi. Then clearly (A(C) + I)f(C) ? 1 if and only if Nf ? 1, and likewise if f is a maximum fractional packing or an FDPF. Note that in the corollary below, the graphs G and H need not have the same order. Corollary 3.6.4 Suppose that G and H have identical cell adjacency matrices for some equitable partitions C1 and C2, respectively. Then G and H belong to the same class. 59 Thus, ?nding equitable partitions can make discovering fractional dominating and pack- ing functions easier. It should be noted that the natural ?reduced? linear program for fractional domination ? Minimize cTx subject to (A(C) + I)x ? 1,x ? 0 where c is the vector (|V1|,...,|Vr|)T ? is no longer the dual to the corresponding ?reduced? program for fractional packing since the cell-adjacency matrix need not be symmetric. Corollary 3.6.4, also gives an alternative proof to Theorem 3.6.1, since two graphs are fractionally isomorphic if and only if they share some equitable partition (see Theorem 2.5.2, from [146]). 3.7 Mycielski graphs As an application of the cell-adjacency matrix, we consider the Mycielski construction, discussed in Chapter 1. The ?rst two Mycielski graphs belong to Class E; P2 and Y (P2) = C5 by regularity; the third and fourth by arguments below. The third Mycielski graph Y (Y (P2)) is called the Gr?otzcsh graph. Using the equitable partition C = {X,Y,{z}}, we solve (A(C) + I)f = 1, by augmenting A(C) + I with 1 and reducing. After reduction we have the FDPF f which assigns the weight of 14 to each of the xi, 18 to each yi and 38 to z. Since f has positive weights on each vertex, Y 2(P2) is in Class E by Corollary 3.3.8. bracketleftBig A(C) + I3 1 bracketrightBig = ? ?? ?? 3 2 0 1 2 1 1 1 0 5 1 1 ? ?? ??? ? ?? ?? 2 8 I3 18 3 8 ? ?? ?? The fourth Mycielski graph Y 3(P2) has an equitable partition D = {C,C?,{z}}, where C is the equitable partition of Y 2(P2) used above, and C? is C applied to {Y}. To solve (A(D) + I)f = 1, we augment A(D) + I with 1 and reduce. After reduction we have the 60 FDPF f with positive weights on each cell of D (and thus each vertex), so Y 3(P2) is in Class E by Corollary 3.3.8. bracketleftBig A(D) + I7 1 bracketrightBig = ? ?? ?? ?? ?? ?? ?? ?? ?? 3 2 0 2 2 0 0 1 2 1 1 2 0 1 0 1 0 5 1 0 5 0 0 1 2 2 0 1 0 0 1 1 2 0 1 0 1 0 1 1 0 5 0 0 0 1 1 1 0 0 0 5 5 1 1 1 ? ?? ?? ?? ?? ?? ?? ?? ?? ? ? ?? ?? ?? ?? ?? ?? ?? ?? 5 27 3 27 7 27 I7 227 1 27 3 27 9 27 ? ?? ?? ?? ?? ?? ?? ?? ?? Conjecture 3.7.1 The kth Mycielski graph is in Class E for all k. GG Y (G) Y (G) Figure 3.12: Y (K1 ?????K1) and Y (P4). Given an arbitrary starting graph G, Y (G) is not necessarily in Class E. If G = P4, the Mycielski Y (P4) is in Class N (see Figure 3.12). If G is a collection of isolates, then Y (G) is the disjoint union of the star K1,n with the collection of isolates, which is in Class P (by Theorem 3.4.2 and Lemma 3.5.1). However, if our starting graph is regular without isolates, we have some results. Theorem 3.7.2 Let G be any regular graph without isolates, then Y (G) is in Class E. 61 Proof. Each x ? X is adjacent to k of the xi and, therefore, k of the yi. Each y ? Y is adjacent to z and k of the xi. Lastly, z is adjacent to n of the yi. Therefore, C = {X,Y,{z}} is an equitable partition. Below we solve (A(C) + I)f = 1. bracketleftbigg A(C) + I3 1 bracketrightbigg = ? ?? ?? ?? k + 1 k 0 1 k 1 1 1 0 n 1 1 ? ?? ?? ??? ? ?? ?? ?? n?1 k2+(n?1)k+n?1 I3 kk2+(n?1)k+n?1 k(k?1)+n?1 k2+(n?1)k+n?1 ? ?? ?? ?? The reduction gives the FDPF f which assigns the weight of n?1k2+(n?1)k+n?1 to each xi, the weight of kk2+(n?1)k+n?1 to each yi, and the weight of k(k?1)+n?1k2+(n?1)k+n?1 to z in Y (G). Since G has no isolates, k > 0 and n > 1; thus each of the three weights are positive. Therefore, Y (G) is in Class E by Corollary 3.3.8. square Theorem 3.7.2 may have a natural generalization: Conjecture 3.7.3 If G is any regular graph without isolates, then Y j(G) ? Class E, for all j ? 0. We end this section with another conjecture, one whose proof will require more than just ?nding a convenient equitable partition. Conjecture 3.7.4 If G is any Class E graph without isolates, then Y (G) ? Class E. 3.8 Miscellaneous graphs Here we present some interesting graphs whose class membership does not follow im- mediately from the preceding theory. Figure 3.13 illustrates two Class E graphs (left), three Class D graphs (center), and two Class N graphs (right). The graph depicted in Figure 3.13(a) is called a pancyclic graph since it has cycles of lengths 3,4,...,n. The function which assigns the weight of 17 to the blue vertices and 27 62 (g)(b) (a) (c) (d) (e) (f) ?1?1 3 ?1 2 0 2 0 ?1 1 2 0 0 0 1 Figure 3.13: (a) A Pancyclic graph, (b) The Moser spindle, (c) A 3-cube with a vertex removed, (d) A wounded spider, (e) A Tree on 6 vertices, (f) A tree on 7 vertices, (g) G3,3 minus a vertex of degree two. otherwise is an FDPF with positive weights on each vertex, so by Corollary 3.3.8, this graph is in Class E. The Moser spindle (also pancyclic) pictured in Figure 3.13(b) is in Class E, since the function which assigns the weight of 16 to the blue vertices and 13 otherwise is an FDPF which has positive weights on each vertex. Let G be the graph obtained from deleting a vertex of a 3?cube (see Figure 3.13(c)). If we assign the weight of 512 to the green vertices, 612 to the blue vertex and 212 to the yellow vertices we have an MFDF f which which has positive weights on each vertex and is not a packing. Therefore by Lemma 3.3.5, G is in Class D. The wounded spider (Figure 3.13(d)) obtained from subdividing two edges of a K1,3 is in Class D, since the constant function of 1 2 is an MFDF which is not packing. For the tree T on 6 vertices (Figure 3.13(e)), if we assign the weight of 12 to the vertices of degree two, and 14 to the vertices of degree one, then 63 we have an MFDF which which has positive weights on each vertex and is not a packing. Therefore by Lemma 3.3.5, T is in Class D. The tree on 7 vertices (Figure 3.13(f)), has x = (2,?1,0,1,0,1,0) as the unique solution of Nx = 1, and is thus Class N. The last Class N graph we give is a 3?3 grid graph with a vertex of degree 2 removed, depicted in Figure 3.13(g). The unique solution to Nx = 1 is x = (?1,2,2,?1,?1,3,0,0). v11 v4 v7 v2 v3 v6 v1 v8 v10v9 v5 Figure 3.14: The Herschel graph. The Herschel graph arises in the study of Hamiltonian algorithms (Figure 3.14). An equitable partition of the vertices is C = {{v1,v11},{v4,v8},{v5,v7},{v2,v3,v9,v10},{v6}}. From the reduction below, we see that the function which assigns the weight of 25 to the vertices {v5,v7} and 15 otherwise is an FDPF. Since each partition receives a positive weight under this FDPF, the Herschel graph is Class E. bracketleftBig A(C) + I5 1 bracketrightBig = ? ?? ?? ?? ?? ?? 1 2 0 2 0 1 2 1 1 0 0 1 0 1 1 2 0 1 1 0 1 1 1 1 0 0 0 4 1 1 ? ?? ?? ?? ?? ?? ? ? ?? ?? ?? ?? ?? 1 5 1 5 I5 25 1 5 1 5 ? ?? ?? ?? ?? ?? 64 3.9 Notes This chapter was joint work with Walsh [153]. Ideally, the ?nal product of this research program would be a complete classi?cation of, if not all graphs, then at least all major families of graphs into our ?ve classes; or creating an algorithm for ?nding the class of a graph. There are several more practical avenues to explore, however. [96] looks at the e?ects of small perturbations of graphs (the addition and deletion of single vertices or edges) on their domination numbers. We could ask similar questions in this setting: given a graph in a given class, what can we say about the class of the graph that results from deleting an edge or a vertex? We are particularly interested in the above question for trees. While categorizing all graphs into the ?ve classes may be overly ambitious, we feel that there should be an accessible algorithmic method for determining the class of any tree. One approach which we have been pursuing is to examine which trees are in Class N, and devising measures for quantifying how far a Class N tree is from being ?partitionable?. The theory of e?cient domination (see [8]), particularly the e?cient fractional domination number, should be applicable here. Recall from Chapter 1, that if there exists an e?cient fractional dominating function on a graph G, then the e?cient fractional domination number, Ff(G) = n. Any fractional e?cient dominating function would also be a fractional packing, since by de?nition, the function g would satisfy g(N[v]) = 1 for all v ? V (G). Thus, any graph G on n vertices in Class I, Class D, Class P, or Class E, would have Ff(G) = n; and if G is Class N, then Ff(G) < n. We end this chapter with a classi?cation of graphs on 5 or fewer vertices. Of the 52 graphs, only 5 do not follow immediately from the preceeding theory or examples: G36, G37, G41, G44, and G48 (graphs are named using the convention in [147]). We classify 65 these graphs below (see Figure 3.15). The rest follow from Theorems 3.4.1, 3.4.2, 3.4.4, Lemma 3.5.1 and Figure 3.6. We give a complete classi?cation of graphs with ?ve or fewer vertices in Appendix C, class by class for convenience and beauty. G44 G48 G36 G37 G41 Class D graphs Class E graphs Figure 3.15: Graphs needed to complete the classi?cation of graphs with 5 or fewer vertices. 66 Chapter 4 Minimum Fractional Total Dominating Functions and Maximum Fractional Open Packing Functions 4.1 Functions which are both minimum fractional total dominating and max- imum fractional open packing In Chapter 1, we saw that ?nding fractional total dominating functions and fractional open packing functions are dual linear programs. As with fractional domination and frac- tional packings in Chapter 3, fractional total domination and fractional open packings are a special dual pair of LPs since the vectors being optimized in both problems can be inter- preted as real-valued functions on the set of vertices. Hence, it becomes possible to have a function whose vector simultaneously solves both the fractional total domination LP and its dual. We call a function which is both a minimum FTDF and a maximum FOPF a fractional total dominating-open packing function (FTD-OPF). Note that a function which is both an FTDF and FOPF is necessarily an MFTDF and an MFOPF and is therefore an FTD-OPF. 34 v1 14v3 0 0 1 1v2 v4 14 34 Figure 4.1: (a) The black vertices form a maximum open packing and a minimum total dominating set, (b) its characteristic function, an FTD-OPF; and (c) an FTD-OPF of C4. 67 4.2 Definition of the classes We wish to investigate the interactions of MFOPFs and MFTDFs. Our ultimate goal is to classify those graphs in which all MFOPFs are FTD-OPFs, or all MFTDFs are FTD- OPFs, or when there are no FTD-OPFs at all, as well as any graphs in between. To do this we de?ne the following ?ve classes based on the intersections of the two following sets: Let D?G be the set of all MFTDFs on G and let P?G be the set of all MFOPFs on G. Every ?nite simple graph without isolates G belongs to exactly one of the classes below: ? G ? Class N? (Null) if D?G ?P?G = ?. ? G ? Class I? (Intersection) if D?G ?P?G negationslash= ?, D?G notsubseteql P?G and P?G notsubseteql D?G ? G ? Class P? (Packing) if D?G subsetnoteql P?G. ? G ? Class D? (Dominating) if P?G subsetnoteql D?G. ? G ? Class E? (Equal) if D?G = P?G. D?G P?G D?G P?G D?GP?G D?G ?P?G D?G ?P?G Class D?Class P? Class N? Class I? Class E? D?G ?P?G D?G ?P?G Figure 4.2: The ?ve classes as di?erent intersections of the sets D?G (in light gray) and P?G (in dark gray); with D?G ?P?G in gray. 68 4.3 The principle of complementary slackness As in Chapter 3, the principal tool that we shall use in our investigations is the Principle of Complementary Slackness (see Theorem 1.3.2). Proposition 4.3.1 (Applied principle of complementary slackness) Let x? be an MFOPF, that is any optimal solution to the linear program: maximize 1Tx subject to Ax ? 1, x ? 0, and let y? be an MFTDF, that is any optimal solution to the dual linear program: minimize 1Ty subject to ATy ? 1, y ? 0. Then x? ? (ATy? ?1) = y? ? (Ax? ?1) = 0. We give the two main consequences below: Corollary 4.3.2 If f is an MFTDF and v ? V (G) for which f(v) > 0, then for any MFOPF g, g(N(v)) = 1. Corollary 4.3.3 If g is an MFOPF and v ? V (G) for which g(v) > 0, then for any MFTDF f, f(N(v)) = 1. These corollaries, in turn, su?ce to establish a number of technical lemmas, which we now state and prove. Lemma 4.3.4 If f is an MFTDF with f(v) > 0 for every vertex v ? V, then every MFOPF is an MFTDF, and thus P?G ? D?G. Proof. Let f be an MFTDF on G with f(v) > 0 for each vertex v. Then by Corollary 4.3.2, every MFOPF g has the property that g(N(v)) = 1 for each vertex v. So g is an MFTDF. square 69 Lemma 4.3.5 If we can find two functions f and g where f is an MFTDF on G with f(v) > 0 for each vertex v, and where g is an MFTDF on G which is not an open packing, then G ? Class D?. Proof. The MFTDF f gives us P?G ? D?G and the MFTDF (non-open packing) g gives us P?G subsetnoteql D?G. square Lemma 4.3.6 If f is an MFOPF with f(v) > 0 for each vertex v ? V, then every MFTDF is an MFOPF, and thus D?G ? P?G. Proof. Let g be an MFOPF on G with g(v) > 0 for each vertex v. Then by Corollary 4.3.3, every MFTDF f has the property that f(N(v)) = 1 for each v. So f is an MFOPF. square Lemma 4.3.7 If we can find two functions f and g where f is an MFOPF on G with f(v) > 0 for each vertex v, and where g is an MFOPF on G which is not total dominating, then G ? Class P?. Proof. The MFOPF f gives us D?G ? P?G and the MFOPF (non-total dominating) g gives us D?G subsetnoteql P?G. square The results of Lemmas 4.3.5 and 4.3.7 also work if there is a single function which has the properties of f and g simultaneously. We need two more lemmas to aid in determining Class N? graphs using analogues of results from [121]. Lemma 4.3.8 If f is an MFTDF and v ? V (G) for which f(N(v)) > 1, then every MFOPF g satisfies g(v) = 0. Proof. Suppose g is an MFOPF with g(v) > 0. Then by Corollary 4.3.3, every MFTDF f satis?es f(N[v]) = 1, a contradiction. square 70 Lemma 4.3.9 If g is an MFOPF and v ? V (G) for which g(N(v)) < 1, then every MFTDF f satisfies f(v) = 0. Proof. Suppose f is an MFTDF with f(v) > 0. Then by Corollary 4.3.2, every MFOPF g satis?es g(N[v]) = 1, a contradiction. square If we can ?nd a function which is both an MFTDF and an MFOPF which has positive weights on each vertex, then combining Lemmas 4.3.4 and 4.3.6 yields: Corollary 4.3.10 For a graph G, if there exists an FTD-OPF f with f(v) > 0 for each vertex v ? V, then G ? Class E?. 4.4 A partial classification Before we begin, we give necessary and su?cient conditions for a graph to be in Class N?. 4.4.1 Class Null? graphs If G is a Class N? graph, then no MFTDF is an MFOPF and no MFOPF is an MFTDF. That is for any graph in Class N? there are no FTD-OPFs on G. Therefore, it is true that no FTDF is a FOPF and no FOPF is a FTDF. There is an easy characterization of Class N? graphs using its adjacency matrix. Proposition 4.4.1 G is in Class N? if and only if the system Ax = 1 has no non-negative solutions. Proof. If Ax = 1 has a non?negative solution, then the vector x is an FTD-OPF, thus G is not in Class N?. Likewise, if G is not in Class N?, then there exists a vector x satisfying Ax = 1, with x ? 0 (each xi is non-negative), thus the system has a non-negative solution. square 71 If we replace N with A in the LP formulation of e?cient fractional domination (1.15), we have the LP formulation of e?cient fractional total domination: maximize 1TAx subject to Ax ? 1, x ? 0 (4.1) Another characterization of Class N? graphs is any graph on n vertices (with no iso- lates) with e?cient fractional total domination number strictly less than n. Proposition 4.4.2 G of order n is in Class N? if and only if the efficient fractional total domination number strictly less than n. With these preliminaries in place, we are ready to begin sorting families of graphs into our ?ve classes. 4.4.2 Regular graphs Theorem 4.4.3 Every regular graph without isolates is Class E?. Proof. Let G be k-regular with no isolates; then the function f(v) = 1k for all v ? V is an FTD-OPF. Since f is nonzero at each vertex, Corollary 4.3.10 tells us that G ? Class E?. square 4.4.3 Trees Theorem 4.4.4 Every Star is class Class E?. Proof. Let G = K1,n. The function which assigns the weight of 1 to the vertex of degree n ? 1 and 1n otherwise is an FTD-OPF. Since this function has positive weights at each vertex G is Class E? by Corollary 4.3.10. square In Chapter 3, we encountered wounded healthy spiders (see Figure 3.3). Healthy spiders are formed from subdividing all of the edges of a K1,t with t ? 2. If we subdivide r edges 72 of a K1,t, we have a wounded spider (with 1 < r < t). We give the proof at the end of Section 4.6. Theorem 4.4.5 If G is a spider with t ? 2 and 1 < r ? t, then G is Class N?. Theorem 4.4.6 Every Double Star is Class P?. Proof. Let G be a double star, a tree on s + t + 2 vertices with a vertex vs of degree s + 1 and a vertex vt of degree t+1 both adjacent to each other; where vs is adjacent to s vertices of degree one and vt is adjacent to t vertices of degree one. The function which assigns the weight of 1 to vs and vt and 0 otherwise is an FTD-OPF. The function which assigns the weight of 1s to the vertices of degree one which are adjacent to vs and 1t to the vertices of degree one which are adjacent to vt is an MFOPF which is not total dominating. By taking the average of the two functions, we get an MFOPF which is not total dominating and has positive weights on each vertex. Thus, by Lemma 4.3.7, G is Class P?. square 12 14 14 18 18 18 18 12 Figure 4.3: An MFOPF which is not total dominating of a double star. 4.4.4 Partial trampolines and generalized Haj?os graphs We revisit two important constructions de?ned in Chapter 1, partial trampolines and the generalized Haj?os graph, [Kn]. Recall that both trampolines and [Kn] are de?ned only for n ? 3. [K3] ?= T(K3) which we will see below is Class P?. Theorem 4.4.7 Let G be the partial trampoline T(Cn), then G is Class P?. 73 Proof. The function f which assigns the weight of 0 to the vertices of degree two (called ui in Chapter 3) and 12 otherwise is an FTD-OPF. The constant function g which assigns the weight of 14 to each vertex is an MFOPF which is not total dominating (since g(N(ui)) = 1 2 < 1 for each i). Thus, by Lemma 4.3.7, G ? Class P ?. square (b)(a) 1 2 01 212 1 2 0 0 1 2 0 0 0 0 1 2 1 2 0 0 0 0 1 2 1 2 1 2 1 2 1 2 0 Figure 4.4: (a) An FTD-OPF and (b) an MFOPF which is not total dominating of the partial trampoline T(C6). Theorem 4.4.8 The generalized Haj?os graph, [Kn] is Class N?, if n ? 4. Proof. The function f which assigns the weight of 0 to each vertex of degree two (called uij in Chapter 3) and 12 otherwise is an FTDF which is not an open packing if n ? 4. The function g which assigns the weight of 1n?1 to the vertices of degree two and 0 otherwise is a FOPF which is not total dominating. Since |f| = |g| = n2, f is an MFTDF and g is an MFOPF. Since f(N(vi)) = n?12 > 1 for all i, by Lemma 4.3.8, every MFOPF h satis?es h(vi) = 0 for all i. Since g(N(uij)) = 1n?1 < 1 then every MFTDF j satis?es j(uij) = 0 for all 1 ? i < j ? n. Therefore, no MFOPF can be an MFTDF, thus [Kn] ? Class N?. square 74 (b)(a) 12 0 14 0 0 0 12 0 0 14 14 14 14 1414 00 0 0 14 14 14 0 00 0 12 12 0 12 Figure 4.5: (a) An MFTDF which is not an open packing and (b) an MFOPF which is not total dominating of the generalized Haj?os graph, [K5]. 4.5 Sums and products of graphs 4.5.1 Disjoint unions Total domination and open neighborhood packing (in both their integer and fractional forms) interact quite simply with disjoint unions as they did with domination and closed neighborhood packing in Chapter 3. Lemma 4.5.1 The function f : V (G ?H) ? [0,1] is a fractional total dominating (open packing) function on G?H if and only if f|G is fractional total dominating (open packing) on G and f|H is fractional total dominating (open packing) on H. Using this, we can determine the class of a disjoint union of two graphs, given the classes of the two starting graphs. The results are easy to check, and are summarized as follows: 4.5.2 Cartesian Products Theorem 4.5.2 P2squareP3k is Class P? for all k > 0. 75 ? Class D? Class E? Class I? Class N? Class P? Class D? Class D? Class D? Class I? Class N? Class I? Class E? Class D? Class E? Class I? Class N? Class P? Class I? Class I? Class I? Class I? Class N? Class I? Class N? Class N? Class N? Class N? Class N? Class N? Class P? Class I? Class P? Class I? Class N? Class P? Table 4.1: Class of the disjoint union of two graphs Proof. Let {pi} = {v1,2,v2,2,...,v1,3k?1,v2,3k?1}. This set induces a partition of V(G) into the open neighborhoods {N(pi)}. The function which assigns 1 to each pi and 0 otherwise is an FTD-OPF. The constant function which assigns the weight of 13 to each vertex is a MFOPF, which is not total dominating. Thus, P2squareP3k is Class P? by Lemma 4.3.7. square 4.6 Fractional isomorphisms and equitable partitions Theorem 4.6.1 If two graphs G and H are fractionally isomorphic, then they belong to the same class. Proof. We proceed by considering the action of the matrix S on a function f; speci?cally, we shall show that Sf has the property of being minimum fractional total dominating (or maximum fractional open packing) on G if f has that property on H. Suppose A and B are adjacency matrices of G and H respectively and S is a doubly stochastic matrix such that AS = SB. Suppose that f is an MFDF on H; then Bf = 1 + ?, where ? ? 0. Then: 76 A(Sf) = (AS)f = (SB)f = S(Bf) = S(1 + ?) = 1 + S? Since both S and ? are non-negative, so is their product. Therefore, Sf is an MFTDF on G (note that Sf is minimum, since |Sf| = |f| and ??f(G) = ??f(H) as shown in Chapter 2.). Further, S? = 0 if and only if ? = 0. Hence, if f is an MFTDF but not an open packing in H, then the same goes for Sf in G. A similar demonstration will reveal that if f is a maximum fractional open packing on H (and thus Bf = 1?? for some nonnegative vector ?), then Sf is a maximum fractional packing on G, and likewise, that the property of being not total dominating is preserved. To complete the proof, note that fractional isomorphism is an equivalence relation, and hence symmetric; speci?cally, if AS = SB then BST = STA. Hence, S sends D?H into D?G, P?H into P?G, and D?H ?P?H into D?G ?P?G. Further, ST sends D?G into D?H, P?G into P?H, and D?G ?P?G into D?H ?P?H, hence the two graphs share a class. square Theorem 4.6.2 Let f be a fractional total dominating (or open packing) function on G. Then fC = S(C)f is a fractional total dominating (open packing) function on G with the property that, if vi and vj belong to the same cell of C, then fC(vi) = fC(vj). The proof is similar to the proof of Theorem 3.6.2. For the graph G in Figure 4.6, the function which assigns the weight of 14 to each of the six blue vertices and 12 to each of the three red vertices is an MFTDF which is not packing, 77 G KH Figure 4.6: Three fractionally isomorphic Class D? graphs. and thus by Lemma 4.3.5, G ? Class D?. G, H and K are all fractionally isomorphic to each other, and are thus in the same class, Class D?. Proof of Theorem 4.4.5. Let r be the number of edges subdivided in a star K1,t. Case 1: r = t. G is obtained by subdividing each edge of a K1,t. If we let H be the head vertex and B and F be the sets of degree two and foot vertices respectively, then {H,B,F} is an equitable partition of G. Let h, b, and f be the weights of the head vertex, degree two and foot vertices respectively. If there existed an FTD-OPF, then there would exist one which satis?ed N(H) = tb = 1 and N(F) = b = 1. This is not possible if t ? 2, therefore the system Ax = 1 has no non-negative solutions. Thus, G is Class N?. Case 2: n = 3k+1. Let G be a wounded spider formed from subdividing 1 < r < t edges of a K1,t. Since we are allowing r subdivisions with 1 < r < t, we must have t ? 3, and thus the head vertex (of degree t) is well de?ned. Consider the equitable partition {H,B,E,F} where H is the cell containing the head vertex, R is the cell containing vertices of degree two, E is the cell containing foot vertices (degree one) which are adjacent to vertices of degree two, and F is the cell containing foot vertices (degree one) which are adjacent to the head vertex. If there existed an FTD-OPF, then there would exist one which satis?ed N(H) = tb + f = 1, N(B) = h + re, N(E) = rb, and N(F) = h = 1. This forces each vertex in R to have weight 1, the head vertex to receive the weight of 1, and thus the 78 function would not be an open packing. Therefore, the system Ax = 1 has no non-negative solutions. Thus, G is Class N?. square Theorem 4.4.5 required the number of subdivided edges 1 < r < t. If t = 2 and r = 1, then we have a path on four vertices. By assigning the weight of 14 to each vertex of degree two and 34 to the vertices of degree one, we have an MFOPF which is not total dominating with positive weights on each vertex, thus P4 ? Class P?. 4.7 The Mycielski construction Theorem 4.7.1 Let G be any regular graph of degree k > 0, then Y (G) is in Class E?. Proof. Each x ? X is adjacent to k of the xi and, therefore, k of the yi. Each y ? Y is adjacent to z and k of the xi. Lastly, z is adjacent to n of the yi. Therefore, C = {X,Y,{z}} is an equitable partition. Below we solve (A(C))f = 1. bracketleftbigg A(C) 1 bracketrightbigg = ? ?? ?? ?? k k 0 1 k 0 1 1 0 n 0 1 ? ?? ?? ??? ? ?? ?? ?? n?k nk I3 1n k n ? ?? ?? ?? The reduction gives the FTD-OPF f which assigns the weight of n?knk to each xi, the weight of 1n to each yi and kn to z in Y (G). Since 0 < k < n, each of the weights are positive. Therefore, Y (G) is in Class E? by Corollary 4.3.10. square 4.8 Notes Every MFTDF is necessarily an FDF, however, not necessarily an MFDF. Every MFPF is necessarily an FOPF, but not necessarily an MFOPF. The question of how the sets of all MFTDFs, MFDFs, MFPFs, and MFOPFs interact may be a di?cult one. However, we can ask a simpler question of when the sets DG and PG interact in the same way as the sets 79 D?G and P?G do. This amounts to asking which graphs without isolates are both in Class X? and Class X (where X is one of: {N,I,P,D,E}). Regular graphs without isolates are both Class E? and Class E. The generalized Haj?os graph [Kn], for n ? 4, is both Class N? and Class N. G15 and G34 are Class D?, but both are Class P (see Appendix C). P5 is Class N?, however, P5 is Class I. In [67], Fisher de?ned the construction u(G) = Y ( ?G) and found a formula for ??f(u(G)); perhaps this construction could be useful in our investigation of the sets D?G and P?G. Just as the strong direct product worked well with MFDFs and MFPFs in Chapter 3, the conjunctive product may work well with MFTDFs and MFOPFs in similar respects. 80 Chapter 5 Domination Null and Packing Null Vertices 5.1 Introduction In Chapter 3, we saw that for some graphs, there were vertices which received a weight of zero for some minimum fractional dominating function. If this happens for all MFDFs, then we have the following de?nition. We call a vertex v ? V (G) domination null i? for every MFDF f on G, f(v) = 0. Similarly, a vertex v ? V (G) is packing null i? for every MFPF g on G, g(v) = 0. Figure 5.1: Domination null vertices (gray), and packing null vertices (red) of [G47]. As an example, let G be the graph G47 in Figure 22, C5 with two nonintersecting chords. Then consider partial generalized Haj?os graph [G47]. The vertices {vi|1 ? i ? n} form a set of packing null vertices in [G47], while {uij|1 ? i < j ? n} is a set of domination 81 null vertices in [G] (with terminology as in Theorem 3.4.13, where the above assertions are proven). The path on 3 vertices P3 is the smallest example of a graph with domination null vertices. The path on 4 vertices P4 is the smallest example of a graph with packing null vertices. The path on 5 vertices P5 is the smallest graph with domination vertices and packing null vertices. In fact, the middle vertex in P5 is both domination null and packing null. Figure 5.2: Packing null vertices (red) of P4. The following consequences of the principle of complementary slackness appear in Chap- ter 3; we restate them here using the language of this chapter. Lemma 5.1.1 If f is an MFDF and v ? V (G) for which f(N[v]) > 1, then v is packing null. Lemma 5.1.2 If g is an MFPF and v ? V (G) for which g(N[v]) < 1, then v is domination null. 5.2 Absence of Domination Null and Packing Null Vertices There are several families of graphs which have no domination null vertices nor packing null vertices. We give partial results on this situation which follow directly from the two Lemmas above. Lemma 5.2.1 For a graph G if there exists an FDPF f with f(v) > 0 for each vertex v ? V then there are no null vertices of either type in G. 82 It follows from the proofs of Theorems 3.4.1, 3.4.3 and 3.7.2 that if G is regular, or G is the complete r-partite graph with parts of size n1,n2,...,nr (with r ? 2 and each nj ? 2), or if G = Y (H) for some regular graph H with no isolates, then G has no null vertices of either type. Conjecture 5.2.2 If G ? Class E, then G has no null vertices (of either type). Corollary 3.3.8 can be restated as the following: if G has no null vertices (of either type), then G ? Class E. If Conjecture 5.2.2 is true, then we would have that G ? Class E i? G has no null vertices (of either type). Conjecture 5.2.3 If a graph G is Class P, then there are no packing null vertices. Lemma 3.3.7 can be restated as: if G has no packing null vertices, and there exists MFPF which is not dominating, then G ? Class P. Conjecture 5.2.4 A graph G is Class D, then there are no domination null vertices. Lemma 3.3.5 can be restated as: if G has no domination null vertices, and there exists MFDF which is not packing, then G ? Class D. Conjecture 5.2.5 IF graph G is Class I, then there exists a vertex which is both domina- tion and packing null. 5.3 Total Domination Null and Open Packing Null Vertices In Chapter 4, we saw that for some graphs, there were vertices which received a weight of zero for some mimimum fractional total dominating function. If this happens for all MFTDFs, then we have the following de?nition. We call a vertex v ? V (G) total domination null if for every MFTDF f on G, f(v) = 0. Similarly, a vertex v ? V (G) open packing null if for every MFOPF g on G, g(v) = 0. 83 For P4, both vertices of degree one are total domination null. For the graph G15 (K3 with an added edge), the vertices of degree two are open packing null. Recall from the proofs of Theorems 4.4.3 and 4.7.1, that if G is regular or G = Y (H) for some regular graph H with no isolates, then G has no total domination null vertices, nor open packing null vertices. Not as much is known about Class I? graphs at this time to state a conjecture similar to Conjecture 5.2.5, however, we do state conjectures on Class E?, Class P?, and Class D? graphs. Conjecture 5.3.1 If a graph G is Class E?, then there are no total domination or open packing null vertices. Conjecture 5.3.2 If a graph G is Class P?, then are no open packing null vertices. Conjecture 5.3.3 If a graph G is Class D?, then there are no total domination null ver- tices. 5.4 Notes Section 5.1 was joint work with Johnson and Walsh. This chapter was based on [121]. In this paper, several theorems are proved and several questions are asked. To conserve trees, we refer the reader to [121] for a fuller account of domination and packing null vertices. 84 Chapter 6 Roman Domination 6.1 Introduction A recent article in Scientific American suggested a new variant of domination; see [170]. A few lesser known articles ([149], [150], and [151]) in the John Hopkins Magazine suggested Roman domination a few years earlier. A Roman dominating function on a graph G is a function f : V ? {0,1,2} which satis?es the property that whenever f(v) = 0, there exists a u ? N(v) for which f(u) = 2. The total weight of a minimum Roman dominating function is ?R. Africa Rome North Iberia Britain Gaul Constantinople Asia Minor Egypt Figure 6.1: The Roman Empire. 85 The Roman domination number ranges from ? ? ?R ? 2?. The only graph on n vertices with Roman domination number equal to its domination number is Kn (see [40]). Graphs with ?R = 2? are called Roman graphs. 6.2 Roman domination as an integer program In [152], ReVelle and Rosing formulate Roman domination as an integer program. For a graph G = (V,E) with V = {v1,...,vn}, for each vi in V , de?ne two {0,1} variables Xi and Yi to be the ?rst and second legions respectively located at vi. In earlier literature, this program is called the Set Covering Deployment Problem, or SCDP. Minimize summationtextni=1 (Xi + Yi) Subject to: Xi ? Yi for all i Xi + summationdisplay vivj?E Yj ? 1 for all i Xi,Yi ? {0,1} for all i (6.1) The ?rst constraint guarantees that the ?rst legion is stationed at a vertex before the second. The ?rst and second constraints guarantee that every vertex either has a legion stationed on it or has a neighbor with two legions stationed on it. The third constraint allows for only entire legions to be stationed. From an optimal solution to the SCDP problem, {X1,Y1,...,Xn,Yn}, we can obtain a minimum Roman dominating function (MRDF) r by letting r(vi) = Xi +Yi for all i. Thus, the value of summationtextni=1 (Xi + Yi), for any optimal solution is equal to ?R. We wish to translate the above IP into matrix terms. If we let v = bracketleftbig X Y bracketrightbigT be the 2n? 1 matrix bracketleftbigX1,...,Xn,Y1,...,YnbracketrightbigT, then (6.1) is equivalent to (6.2) below. 86 Minimize bracketleftbigg 1T 1T bracketrightbigg ? ?? X Y ? ?? Subject to: ? ?? In A In ?In ? ?? ? ?? X Y ? ??? ? ?? 1 0 ? ?? v ?{0,1} vector (6.2) We can relax the condition that v be a {0,1} vector, and instead require that the entries be non-negative. Then the integer program (6.2) becomes a linear program. The value of 1Tv for any optimal solution of (6.3) is equal to the fractional (open neighborhood) Roman domination number, ?R?f(G). Minimize bracketleftbigg 1T 1T bracketrightbigg ? ?? X Y ? ?? Subject to: ? ?? In A In ?In ? ?? ? ?? X Y ? ??? ? ?? 1 0 ? ?? v ? 0 (6.3) The reason for the parenthetical remark ?open neighborhood? and the use of ??? in the notation will become apparent in Section 6.3. 87 6.2.1 Beamers and buffers The dual linear program of fractional (open neighborhood) Roman domination (6.3) is given below, where bracketleftbig 1 0 bracketrightbigT is the 2n?1 matrix with the 1 as the ?rst n entries and 0 as the next n entries, and uT as the 2n? 1 matrix bracketleftbig W Z bracketrightbigT. Maximize bracketleftbigg 1T 0T bracketrightbigg ? ?? W Z ? ?? Subject to: ? ?? In In A ?In ? ?? ? ?? W Z ? ??? ? ?? 1 1 ? ?? u ? 0 (6.4) The value of the above linear program is the fractional (open neighborhood) Roman domi- nation number. The integer program is then: Maximize bracketleftbigg 1T 0T bracketrightbigg?? ? W Z ? ?? Subject to: ? ?? In In A ?In ? ?? ? ?? W Z ? ??? ? ?? 1 1 ? ?? u ?{0,1} vector (6.5) The value of this integer program will be called the (open neighborhood) beamer bu?er number, denoted by ??R. Thus, we have ??R(G) ? ?R?f(G) ? ?R(G), for all graphs G. 88 There is an interesting story to go along with the dual linear program of Roman dom- ination. On the planet Zelgon, the cities are connected to one another in a network or graph. The beings of Zelgon want to emit as much total light as possible with the following constraints. At any location vi a light emits Wi units of radiation, not to the inhabitants of its location, but to each of its neighbors. According to a pilot study, it has been determined that the inhabitants of planet Zelgon can handle at most one unit of radiation safely. To enable more light, there is a free bu?er material (from the planet?s abundant supply of straw) that any location vi, with Wi < 1, may be used to reduce the amount of radiation by Zi units (with Zi at most 1 ?Wi). We illustrate the above with an example, with G = C5. If we let Y1 = 1 (which forces X1 = 1) and X3 = X4 = 1 and all other Xi and Yi be zero, then we have ?R ? 4. The function f(vi) = Xi+Yi is in fact a minimum Roman dominating function, or an MRDF. To compute ?R?f of C5, we seek to minimize the sum summationtext5i=1 (Xi + Yi) subject to the constraints: Xi ? Yi for all i, X1 + Y5 + Y2 ? 1 X2 + Y1 + Y3 ? 1 X3 + Y2 + Y4 ? 1 X4 + Y3 + Y5 ? 1 X5 + Y4 + Y1 ? 1 89 If we let Xi = Yi = 13, we have ?R?f ? 103 . Now we verify by ?nding an optimal solution to the dual LP: maximize summationtext5i=1 Wi, subject to Wi + Zi ? 1, W5 + W2 ?Z1 ? 1 W1 + W3 ?Z2 ? 1 W2 + W4 ?Z3 ? 1 W3 + W5 ?Z4 ? 1 W4 + W1 ?Z5 ? 1 If we let Wi = 23 and Zi = 13, we have ??Rf ? 103 . Thus, ?R?f = 103 , and f(v) = parenleftbig13, 13parenrightbig for all v is an MFRDF of C5. In [40], it was shown that ?R(Cn) = ceilingleftBig2n 3 ceilingrightBig . Theorem 6.2.1 ?R?f(Cn) = 2n3 . Proof. Suppose G is a cycle on n vertices. If we let Xi = Yi = 13, for 1 ? i ? n, this is a solution to (6.3) with total weight 2n3 . Therefore, ?R?f(Cn) ? 2n3 . Wi = 23 and Zi = 13 for 1 ? i ? n, is a solution to the dual LP (6.4), with total weight summationtextni=1 Wi = 2n3 . From this, we have that ?R?f(Cn) ? 2n3 . Thus, ?R?f(Cn) = 2n3 . square 6.3 Closed neighborhood fractional Roman domination In the previous section, traveling armies (or portions of) could not defend the location which they were stationed at, a situation which is ambiguous in the integer Roman domina- tion problem. In the integer case, if there is a traveling army stationed at a location, then there is a full home army stationed as well. In the event of an attack on this location, the traveling army need not defend the home. We give the integer programming formulation of closed neighborhood Roman domination below. By the remark above, the value of (6.6) is 90 equal to the value of (6.3); that is, if we replace A in with N in (6.3), the value of the IP is unchanged. Minimize bracketleftbigg 1T 1T bracketrightbigg?? ? X Y ? ?? Subject to: ? ?? In N In ?In ? ?? ? ?? X Y ? ??? ? ?? 1 0 ? ?? v ?{0,1} vector (6.6) We can relax the condition that v be a {0,1} vector, and instead require that the entries be non-negative. Then the integer program (6.6) becomes a linear program. The value of 1Tv for any optimal solution of (6.7) is equal to the fractional (closed neighborhood) Roman domination number, ?Rf(G). Minimize bracketleftbigg 1T 1T bracketrightbigg ? ?? X Y ? ?? Subject to: ? ?? In N In ?In ? ?? ? ?? X Y ? ??? ? ?? 1 0 ? ?? v ? 0 (6.7) 6.3.1 Closed neighborhood beamers and buffers The circumstances for the dual LP also change when closed neighborhoods are used. So now the radiation emitted from a location is felt at that location. The dual linear program 91 of fractional (closed neighborhood) Roman domination (6.7) is given below, where [ 1 0 ]T is the 2n? 1 matrix with the 1 as the ?rst n entries and 0 as the next n entries. Maximize bracketleftbigg 1T 0T bracketrightbigg?? ? W Z ? ?? Subject to: ? ?? In In N ?In ? ?? ? ?? W Z ? ??? ? ?? 1 1 ? ?? u ? 0 (6.8) The value of the above linear program is the fractional (closed neighborhood) Roman dom- ination number. The integer program is then: Maximize bracketleftbigg 1T 0T bracketrightbigg ? ?? W Z ? ?? Subject to: ? ?? In In N ?In ? ?? ? ?? W Z ? ??? ? ?? 1 1 ? ?? u ?{0,1} vector (6.9) The value of this integer program will be called the (closed neighborhood) beamer bu?er number, denoted by ?R. Thus, we have ?R(G) ? ?Rf(G) ? ?R(G), for all graphs G. Theorem 6.3.1 ?Rf(Cn) = n2. Proof. Suppose G is a cycle on n vertices. If we let Xi = Yi = 14, for 1 ? i ? n, this is a solution to (6.7) with total weight n2. Therefore, ?Rf(Cn) ? n2. Wi = Zi = 12, for 1 ? i ? n, 92 is a solution to the dual LP (6.8), with total weight summationtextni=1 Wi = n2. From this, we have that ?Rf(Cn) ? n2. Thus, ?Rf(Cn) = n2. square 6.4 Fractional isomorphisms revisited Roman domination is a non?invariant parameter with respect to fractional isomor- phism. Recall that any two k?regular graphs on n vertices are fractionally isomorphic, and so C9 ?=f C4?C5. However, ?R(C9) = 6, while ?R(C4?C5) = 7 (See Figure 14 in Appendix B). We will show that both forms of fractional Roman domination are invariant parameters. Theorem 6.4.1 Let S be a fractional isomorphism from G to H and f(v) = bracketleftbig X Y bracketrightbigT be a fractional open (respectively closed) Roman dominating function on H. Then f(v) = bracketleftbig SX SY bracketrightbigT is a fractional open (respectively closed) Roman dominating function on G. Proof. Let A and B be the adjacency matrices of G and H so that AS = SB. Let M represent B for fractional open neighborhood Roman domination or N = B + I for fractional closed neighborhood Roman domination on H. Let M? represent A for frac- tional open neighborhood Roman domination or N = A + I for fractional closed neigh- borhood Roman domination on G. Let R = ? ?? In M In ?In ? ?? and S ? S = ? ?? S 0 0 S ? ??. Suppose bracketleftbig X Y bracketrightbigT is an FRDF on H. Then Rbracketleftbig X Y bracketrightbigT ? bracketleftbig 1 0 bracketrightbigT. This im- plies that Rbracketleftbig X Y bracketrightbigT = bracketleftbig 1 0 bracketrightbigT + ?, for some non-negative vector ?. Note that (S?S)bracketleftbig 1 0 bracketrightbigT = bracketleftbig S1 S0 bracketrightbigT = bracketleftbig 1 0 bracketrightbigT and (S?S)? is non-negative. Furthermore, we have the sum of the entries of (S?S)bracketleftbig X Y bracketrightbigT is the sum of the entries ofbracketleftbig X Y bracketrightbigT. Hence, if we can show that (S ?S)R = R(S ?S), then we are done.? ?? S 0 0 S ? ?? ? ?? In M In ?In ? ?? = ? ?? S SM S ?S ? ?? = ? ?? S M?S S ?S ? ?? = ? ?? In M? In ?In ? ?? ? ?? S 0 0 S ? ?? square 93 Corollary 6.4.2 ?R?f and ?Rf are invariant parameters. Proof. If we let f be a minimum FRDF (open or closed), then Theorem 6.4.1 gives ?R?f(G) ? ?R?f(H) and ?Rf(G) ? ?Rf(H). If we replace S with ST, then we have if f(v) = bracketleftbig X Y bracketrightbigT is a fractional open (respectively closed) Roman dominating function on G, then f(v) = bracketleftbig STX STY bracketrightbigT is a fractional open (respectively closed) Roman dominating function on H. Thus, if f is a minimum FRDF (open or closed), then ?R?f(G) ? ?R?f(H) and ?Rf(G) ? ?Rf(H). square Corollary 6.4.3 Let C be an equitable partition on V (G). Then there exists a minimum fractional (open, respectively closed) Roman dominating function which is constant on each cell of the partition C. v9 v5 v2 v4 v3 v1v6 v7 v8 Figure 6.2: A Roman graph G. As an example, the Roman graph above has nine vertices, thus ?nding ?R?f would require solving 18 equations in 18 variables Xi and Yi. We will use only four. We will use the equitable partition of the vertices {{v1,v2,v3,v4,v5,v6},{v7,v8,v9}}, as before. The four variables we will need are: Yr, Xr, Yb, Xb, which represent fractions of ?rst and second legions on the red vertices and then blue vertices, respectively. We seek to minimize 94 6(Xr + Yr) + 3(Xb + Yb) subject to: Xr ? Yr Xb ? Yb Xr + 2Yr + Yb ? 1 Xb + 2Yr + 2Yb ? 1 We can see that Xr = Yr = 27 and Xb = Yb = 17 is a solution. To see that it is an optimal solution, we check the dual LP. For the dual, we seek to maximize: 6Wr + 3Zb subject to: Wr + Zr ? 1 Wb + Zb ? 1 2Wr + Wb ?Zr ? 1 2Wr + 2Wb ?Zb ? 1 We can see that Wr = 47,Zr = 37, Wb = 27, and Zb = 57 is a solution, with total weight 30 7 . Thus, the function f(vi) = parenleftbig2 7, 2 7 parenrightbig for 1 ? i ? 6 and f(v i) = parenleftbig1 7, 1 7 parenrightbig for 7 ? i ? 9 is a minimum fractional (open neighborhood) Roman dominating function, with a total weight of ?R?f(G) = 307 . For the fractional (closed neighborhood) Roman domination number of the above Ro- man graph G we seek to minimize 6(Xr + Yr) + 3(Xb + Yb) subject to: Xr ? Yr Xb ? Yb Xr + 3Yr + Yb ? 1 Xb + 3Yr + 2Yb ? 1 95 We can see that Xr = Yr = 29 and Xb = Yb = 19 is a solution. To see that it is an optimal solution, we check the dual LP. For the dual, we seek to maximize: 6Wr + 3Zb subject to: Wr + Zr ? 1 Wb + Zb ? 1 3Wr + Wb ?Zr ? 1 3Wr + 2Wb ?Zb ? 1 We can see that Wr = 49,Zr = 59, Wb = 29, and Zb = 79 is a solution, with total weight 30 9 . Thus, the function f(vi) = parenleftbig2 9, 2 9 parenrightbig for 1 ? i ? 6 and f(v i) = parenleftbig1 9, 1 9 parenrightbig for 7 ? i ? 9 is a minimum fractional (closed neighborhood) Roman dominating function, with a total weight of ?Rf(G) = 309 . On page 28, we saw that the Roman graph G above is fractionally isomorphic to P3squareC3. Thus, we have also found ?Rf(P3squareC3) = 307 and ?R?f(P3squareC3) = 309 . Note that ?R(P3squareC3) = 5. If G is a Roman graph (?R = 2?), then ?R?f is not necessarily twice ??f, nor is ?Rf necessarily twice ?f. The above example veri?es this, since ??f(G) = 3. Note that ?f(G) = 15 7 , which is half of the fractional (open neighborhood) Roman domination number of 30 7 . 6.5 Legion mobilization Is it possible to rearrange the vertices of a dominating set to obtain a di?erent variation of domination? Consider the weights on the vertices in the characteristic function of a dominating set. If we allow the movement of a weight on a vertex to a vertex distance one away, we call this movement a mobilization of the weight. If we allow any of the weights to be moved at most once to vertices distance one away, we have a mobilization of the 96 dominating function. In [40], MRDFs are represented by three sets: V0 is the set of vertices which receive no legions, V1 is the set of vertices which receive precisely one legion, and V2 is the set of vertices which receive two legions. The proof of Theorem 6.5.1 is due to Goddard, Hedetniemi ([98]) and Rubalcaba. Figure 6.3: Mobilize some of the legions of an MRDF to obtain a total dominating set. Theorem 6.5.1 If f is a minimum Roman dominating function, having a maximum num- ber of vertices with two legions, on a graph without isolates, then there exists a way to mobilize the legions (by movements of distance at most one) to achieve a total dominating set. Proof. Let f = (V0,V1,V2) be an MRDF having a maximum number of vertices in the set V2. One can assume, therefore, that V2 dominates the set V0 and that V1 is an independent set, every vertex in which is adjacent to at least one vertex in V0 and no vertices in V2. Let the vertices of V1 be {u1,u2,...,uk} and let the vertices of V2 be {v1,v2,...,vj}. For i = 1 to k do: move the legion at vertex ui to a neighboring vertex in V0 which has no legion yet. If no such vertex in V0 is available, then delete this legion. For i = 1 to j do: move one legion at vertex vi to a neighboring vertex in V0 which has no legion yet. If no such vertex in V0 is available, then delete this legion. The resulting placement of legions will be a total dominating set, since: each vertex in the original set V1 now has no legion, but is adjacent to at least one vertex in V0 having 97 one legion; each vertex in V0 is adjacent to at least one vertex in V2 now having one legion; and each vertex in V2 is adjacent to at least one vertex in V0 now having one legion. square Figure 6.4: Mobilize some of the legions of an MRDF to obtain a total dominating set. Observe that starting from right to left in Figure 6.4, we start with a minimum double dominating function, then move three legions (in the reverse direction of the arrows) to obtain a Roman dominating function. This is not always possible, however. The graph in Figure 6.5 shows that ?R(G) can be larger than the double domination number dd(G). In the ?gure below, dd([C5]) = 5, whereas ?R([C5]) = 7. (b)(a) Figure 6.5: (a) The legions form a MRDF and (b) the red vertices form a minimum double dominating set of the partial generalized Haj?os graph [C5] 98 6.5.1 Bounds on ?R In [40], upper and lower bounds of the Roman domination number are found in terms of the minimum and maximum degree for any graph without isolates. [40] 2n? + 1 ? ?R ? n parenleftBigg 2 + ln (1 + ?2) ? + 1 parenrightBigg Corollary 6.5.2 If G contains no isolates, then ?t(G) ? ?R(G), furthermore, this bound is sharp. Proof. From Theorem 6.5.1, we have ?t(G) ? ?R(G) for all graphs G without isolates, since certain MRDFs (with a maximum number of vertices with weight 2) can be turned into TDFs with total weight less than or equal to ?R(G). To see that the above bound is sharp, note that ?t(C3) = ?R(C3) = 2. square In [94], a {k}?dominating function is de?ned as a function g : V ? {0,1,...,k} which satis?es g(N[v]) ? k for every v ? V (G). The {k}?domination number, ?{k} is the minimum weight of a {k}?dominating function. Figure 6.5 shows that ?R is not bounded above by ?{2}, since if we let the red vertices get the weight of 1 and 0 otherwise, we have a {2}?dominating function with total weight 5 < ?R = 7. In [55], it was shown that for any graph G and any positive integer k ? 2, ?f(G) ? ?{k}(G) k ? ?(G). In fact, an equivalent de?nition of the fractional domination number is: ?f(G) = limk???{k}(G)k . Corollary 6.5.3 If G contains no isolates, then for any integer k ? 2: ?f(G) ? ?{k}(G)k ? ?(G) ? ?t(G) ? ?R(G) ? 2?(G) 99 A graph parameter ?(G) is not comparable to another parameter ?(G) if there exists graphs G and H so that ?(G) < ?(G) and ?(H) > ?(H). There are several parameters which are not comparable to ?R; in Theorem 6.5.4, we list a few domination parameters which are not comparable to ?R. In Theorem 6.5.4, ?(G) refers to the maximum cardinality of a minimal dominating set in G; ?c(G) is the minimum cardinality of a connected dominating set; ?2(G) is the minimum cardinality of a 2-dominating set S on G (every vertex outside of S is adjacent to two distinct members of S); and ?res refers to the restrained domination number, the minimum cardinality of a set S of vertices which dominate V (G) and has the property that every vertex outside of S is adjacent to another vertex outside of S (note that ?r is used for both the restrained domination number and the weak Roman domination number in the literature). Since any connected dominating set with two or more vertices is also a total dominating set, ?t(G) ? ?c(G) for all G with ?(G) < n? 1 ([94]). However, as we will see below, the connected domination number is not comparable to the Roman domination number. Theorem 6.5.4 The domination parameters: ?, ?c, ?2, dd, ?{2}, and ?res are not compa- rable to the Roman domination number. Proof. Upper domination and Roman domination numbers are not comparable, since ?(C6) = 3 < ?R(C6) = 4, but ?(K1,3) = 3 > ?R(K1,3) = 2. The connected domination and Roman domination numbers are not comparable, since ?c(P4) = 2 < ?R(P4) = 3, while, ?c(C9) = 7 > ?R(C9) = 6. The parameters ?R(G) and ?2(G) are not comparable, since ?2(C6) = 3 < ?R(C6) = 4, whereas ?2(K1,3) = 4 > ?R(K1,4) = 2. The double domination number can be quite a bit larger than ?R, for instance, dd(K1,6) = 7 > ?R(K1,6) = 2. Figure 6.5, shows that ?R can be larger than the double domination number. Since ?{2}(G) ? dd(G) (for all graphs G without isolates), the {2}-domination number can be smaller than ?R. For the path on four vertices, we have ?{2}(P4) = 4 > ?R(P4) = 3. 100 The restrained domination and Roman domination numbers are not comparable, since ?res(C5) = 3 < ?R(C5) = 4, while, ?res(K1,3) = 4 > ?R(K1,3) = 2 square 6.6 Notes The original work in sections 6.1 ? 6.4 was joint work with Walsh [177]. Section 6.5 was joint work with Goddard and Hedetniemi [98]. The weak Roman domination number ?r(G) (de?ned in [99]), is shown to be at most the Roman domination number for any graph G. The total domination number and weak Roman domination number are not comparable, since ?r(P5) = ceilingleftBig3(5) 7 ceilingrightBig = 3 < ?t(P5) = 4, whereas ?r(C9) = ?R(C9) = 6 > ?t(C9) = 5. Since both total and weak Roman domination numbers are at least the domination number and at most the Roman domination number, ?r can replace ?t in the chain in Corollary 6.5.3, and we have for any integer k ? 2: ?f(G) ? ?{k}(G)k ? ?(G) ? ?r(G) ? ?R(G) ? 2?(G), for all G with ? ? 2 Some of the parameters which were not comparable to the Roman domination number may serve as bounds on ?R, with extra requirements, like minimum degree at least two or higher. Also, ?{2} was found to be not comparable with ?R. What if we try to compare ?{k} for other values of k > 2 with ?R? Can we show that the total domination number is bounded above by either ?R?f or ?Rf? For which isolate-free graphs G, other than C3 or C6, do we have ?t(G) = ?R(G)? [21] should be of use here. 101 Chapter 7 Open Problems 7.1 Open problems We give several open questions organized by chapter. Johnson o?ers the prize of ?a six-pack of beverages? to any one who can either prove Conjecture 5.2.2 or ?nd a counter- example (see page 83). 7.1.1 Open problems from Chapter 2 ? If G ?=f H, then are their upper fractional domination numbers the same? (see [94]) ? If G ?=f H, then are their fractional intersection numbers the same? (see [157]) ? If G is fractionally Hamiltonian, H is connected, and G ?=f H, then is H necessarily fractionally Hamiltonian? (see [157]) ? Which invariant properties or parameters with respect to semi-isomorphism are non- invariant with respect to fractional isomorphism? 7.1.2 Open problems from Chapter 3 ? Find an algorithm to ?nd the Class of any graph. 7.1.3 Open problems from Chapter 4 ? Find an algorithm to ?nd the Class* of any graph without isolates. 102 7.1.4 Open problems from Chapter 5 ? Is the converse to Theorem 1.3.2 true? If not, is the converse to either Proposition 3.3.1 or Proposition 4.3.1 true? ? Are Conjectures 5.2.2?5.3.3 true? 7.1.5 Open problems from Chapter 6 ? We have the following bounds for ?R?f and ?Rf: ??R ? ?R?f ? ?R and ?R ? ?Rf ? ?R. Can these bounds be improved? 7.2 Conclusion We have seen the bene?ts of not only investigating parameters, but also the optimal solutions which yield the value of a parameter (integer or fractional). Much of the research which focuses on the values of a particular parameter for various graphs, bounds on the parameter based on properties of the graph and/or with other parameters, could greatly bene?t from this type of investigation. For example, we obtained the new bound ?t ? ?R (for any graph without isolates) by rearranging weights of optimal solutions of one problem into the other. At press time of this dissertation, the articles by ReVelle [149], [150], [151], and a note by Peterson [145], were available online at: [149] http://www.jhu.edu/?jhumag/0497web/locate3.html [150] http://www.jhu.edu/?jhumag/0697web/revelle.html [151] http://www.jhu.edu/?jhumag/0997web/roman.html [145] http://www.maa.org/mathland/mathtrek 9 11 00.html 103 Bibliography [1] R. Aharoni, Fractional matchings and covers in in?nite hypergraphs, Combinatorica 5 (1985) 181?184. [2] D. Archdeacon, J. Ellis-Monaghan, D. C. Fisher, D. Froncek, P. C. B. Lam, S. Seager, B. Wei, and R. Yuster, Some remarks on domination, Journal of Graph Theory 46 (2004) 207?210. [3] J. Arquilla and H. Fredricksen, ?Graphing? an Optimal Grand Strategy Military Operations Research 1 no. 3 (1995), 3-17. [4] R. Balakrishnan, The energy of a graph, Linear Algebra and its Applications 387 (2004) 287?295. [5] K. T. Bali?nska, S. K. Simi?c, and K. T. Zwierzy?nski, Which non?regular bipartite interval graphs with maximum degree four do not have ?1 as eigenvalues?, Discrete Mathematics 286 (2004) 15?24. [6] D. W. Bange, A. E. Barkauskas, and P. J. Slater, Disjoint dominating sets in trees, Sandia Laboratories Report SAND 78 ? 1087J (1973). [7] D. W. Bange, A. E. Barkauskas, and P. J. Slater, E?cient dominating sets in graphs, in R. D. Ringeisen and F. S. Roberts (Eds.) Applications of Discrete Mathematics, pages 189?199, SIAM, Philadelphia, PA, 1988. [8] D. W. Bange, A. E. Barkauskas, L. H. Host, and P. J. Slater, Generalized domination and e?cient domination in graphs, Discrete Mathematics 159 (1996) 1?11. [9] D. W. Bange, L. H. Host, and P. J. Slater, E?cient near-domination of grid graphs, Congressus Numerantium 58 (1987) 83?92. [10] L. B. Beasley and S. -G. Lee, Linear operators preserving multivariate majorization, Linear Algebra and its Applications 304 (2000) 141?159. [11] L. B. Beasley, S. -G. Lee, and Y. -H. Lee, A characterization of strong preservers of matrix majorization, Linear Algebra and its Applications 367 (2003) 341?346. [12] C. Berge, Balanced matrices, Mathematical Programming 2 (1972) 19?31. [13] J. R. S. Blair, P. Heggernes, S. B. Horton, and F. Manne, Broadcast domination algo- rithms for interval graphs, series-parallel graphs, and trees, Congressus Numerantium 169 (2004) 55?77. 104 [14] P. Blitch and D. P. Sumner, Domination critical graphs, Journal of Combinatorial Theory Series B 34 (1983) 65?76. [15] A. Bohannon, P. D. Johnson Jr., J. Lanig, and R. R. Rubalcaba, The chromatic numbers of some Euclidean distance graphs, Geombinatorics 10 (2001) 141?164. [16] B. Bollob?as, Modern Graph Theory, Springer, New York, NY, 1998. [17] J. A. Bondy and U. S. R. Murty, Graph Theory and Related Topics, Academic Press, New York, NY, 1979. [18] M. Boroweicki and D. Michalak, Generalized independence and domination in graphs, Discrete Mathematics 191 (1998) 51?56. [19] M. Boroweicki, D. Michalak, and E. Sidorowicz, Generalized domination, indepen- dence and irredundance, Discussiones Mathematicae Graph Theory 17 (1) (1997) 143?153. [20] E. D. Boyer, D. C. Fisher, and P. A. McKenna, Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski graphs, Discrete Applied Mathematics 84 (1998) 93?103. [21] R. C. Brigham, J. R. Carrington, and R. P. Vitray, Connected graphs with maximum total domination number, Journal of Combinatorial Mathematics and Combinatorial Computing 34 (2000) 81?95. [22] A. E. Brouwer, P. Duchet, and A. Schrijver, Graphs whose neighborhoods have no special cycles, Discrete Mathematics 47 (1983) 177?182. [23] R. A. Brualdi, Some applications of doubly stochastic matrices, Linear Algebra and its Applications 107 (1988) 77?100. [24] R. L. Bul?n, private communication (2005). [25] G. J. Chang and C. -S. Liao, k?tuple domination in graphs, Information Processing Letters 87 (2003) 45?50. [26] G. J. Chang and G. L. Nemhauser, The k-domination and k-stability problems on sun-free chordal graphs, SIAM Journal of Algebraic Discrete Methods 5 (1984) 332? 345. [27] J. M. Chang, Y. Cheng, J. S. Yang, and Y. L. Wang, Panconnectivity, fault-tolerant Hamiltonian-connectivity in alternating group graphs, Networks 44 (2004), 302?310. [28] T. Y. Chang, Domination numbers of grid graphs, Ph.D. Thesis, University of South Florida, 1992. [29] G. Chartrand, Introductory Graph Theory, Dover Publications Inc., New York, NY, 1977. [30] G. Chartrand and L. Lesniak, Graphs and Digraphs, Chapman & Hall CRC, New York, NY, 2004. 105 [31] G. G. Chappell, J. Gimbel, C. Hartman, Approximating the dominating number of a graph, in preparation. [32] X. Chen, L. Sun, and H. Xing, Characterization of graphs with equal domination and connected domination numbers, Discrete Mathematics 289 (2004) 129?135. [33] R. Ch?eri?, S. Gravier, X. Lagraula, C. Payan, and I. Zighem, Domination number of the cross product of paths, Discrete Applied Mathematics 94 (1999) 101?139. [34] G. A. Cheston and G. Fricke, Classes of graphs for which upper fractional domination equals independence, upper domination, and upper irredundance. Discrete Applied Mathematics 55 (1994) 241?258. [35] V. Chv?atal, Linear Programming, W.H. Freeman & Company, New York, NY, 1983. [36] F. R. K. Chung, Spectral Graph Theory, Regional Conference Series in Mathematics No. 92, AMS, Reprinted 1997. [37] S. A. Clark, private communication (2005). [38] F. H. Clarke and R. E. Jamison, Multicolorings, measures, and games on graphs, Discrete Mathematics 14 (1976) 241?245. [39] E. J. Cockayne, R.M. Dawes, and S. T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211?219. [40] E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi, and S. T. Hedetniemi, Roman domination in graphs, Discrete Mathematics 278 (2004) 11?22. [41] E. J. Cockayne, O. Favaron, and C. M. Mynhardt, Secure domination, weak Roman domination and forbidden subgraphs, Bulletin of the Institute of Combinatorics and its Applications 39 (2003) 87?100. [42] E. J. Cockayne, P. J. P. Grobler, W. Gr?undlingh, J. Munganga, and J. H. van Vuuren, Protection of a graph, Utilitas Mathematica 67 (2005) 19?32. [43] E. J. Cockayne, G. MacGillivray, and C. M. Mynhardt, Convexity of minimal domi- nating functions of trees?II, , Discrete Mathematics 125 (1994) 137?146. [44] E. J. Cockayne and C. M. Mynhardt, Convexity of minimal dominating functions of trees- a survey, Quaestiones Mathematiae 16 (1993) 301?317. [45] E. J. Cockayne and C. M. Mynhardt, A charaterisation of universal minimal total dominating functions in trees, Discrete Mathematics 141 (1995) 75-84. [46] E. J. Cockayne, C.M. Mynhardt, and B. Yu, Total dominating functions in trees: minimality and convexity. Journal of Graph Theory 19 (1995) 83?92. [47] D. G. Collins, Canonincal forms for the digraph isomorphism problem, in Y. Alavi, G. Chartrand, O. R. Oellermann and A. J. Schwenk (Eds.), Graph Theory, Combina- torics, and Applications, Proceedings of the Sixth Quadrennial International Confer- ence on the Theory and Applications of Graphs, vol. 1, pages 563?584, (Kalamazoo, MI 1988), Wiley Publications, 1991. 106 [48] D. G. Corneil and R. C. Read, The graph isomorphism disease, Journal of Graph Theory 1 (1977) 339?363. [49] E. Dahlhaus, P. D. Manuel, and M. Miller, A characterization of strongly chordal graphs, Discrete Mathematics 187 (1998) 269?271. [50] P. Dankelmann, J. H. Hattingh, M. A. Henning, and H. C. Swart, Trees with equal domination and restrained domination numbers, submitted. [51] P. A. Dreyer, Jr., Applications and variations of domination in graphs, Ph.D. Thesis, Rutgers University, October 2000. [52] G. S. Domke, D. C. Fisher, J. Ryan, and A. Majumdar, Fractional domination of strong direct products, Discrete Applied Mathematics 50 (1994) 89?91. [53] G. S. Domke, J. H. Hattingh, S. T. Hedetniemi, R. C. Laskar, and L. R. Markus, Restrained domination in graphs, Discrete Mathematics 203 (1999) 61?69. [54] G. S. Domke, S. T. Hedetniemi, and R. C. Laskar, Fractional packings, coverings and irredundance in graphs, Congressus Numerantium 66 (1988) 227?238. [55] G. S. Domke, S.T. Hedetniemi, R. C. Laskar, and G. Fricke, Relationships between integer and fractional parameters of graphs, in Y. Alavi, G. Chartrand, O. R. Oeller- mann and A. J. Schwenk (Eds.), Graph Theory, Combinatorics, and Applications, Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, vol. 1, pages 371?387, (Kalamazoo, MI 1988), Wiley Publi- cations, 1991. [56] G. S. Domke and R. C. Laskar, The bondage and reinforcement numbers of ?f for some graphs, Discrete Mathematics 167/168 (1997) 249?259. [57] G. S. Domke, G. Fricke, R. C. Laskar, and A. Majumdar, A fractional view of graph theory, Sankhy?a: The Indian Journal of Statistics 54 (1992) 265?279. [58] J. E. Dunbar, D. G. Ho?man, R. C. Laskar, and L. R. Markus, ??Domination, Discrete Mathematics 211 (2000) 11-26. [59] M. Faber, Independent domination in chordal graphs, Operations Research Letters 1 (1982) 134-138. [60] M. Faber, Characterizations of strongly chordal graphs, Discrete Mathematics 43 (1983) 173-189. [61] M. Faber, Domination, independent domination, and duality in strongly chordal graphs, Discrete Applied Mathematics 7 (1984) 115?130. [62] O. Favaron, M. A. Henning, Upper total domination in claw?free graphs, Journal of Graph Theory 44 (2003) 148-158. [63] O. Favaron, On a conjecture of Fink and Jacobson concerning k?domination and k?dependence, Journal of Combinatorial Theory Series B 39 (1985) 101?102. 107 [64] O. Favaron, M. A. Henning, C. M. Mynhardt, and J. Puech, Total domination in graphs with minimum degree three, Journal of Graph Theory 34 (2000) 9?19. [65] M. Fischermann, Block graphs with unique minimum dominating functions, Discrete Mathematics 240 (2001) 274?251. [66] D. C. Fisher, Domination, fractional domination, 2-packing and graph products, SIAM Journal of Discrete Mathematics 7 (1994) 493?498. [67] D. C. Fisher, Fractional dominations and fractional total dominations of graph com- plements, Discrete Applied Mathematics 122 (2002) 283?291. [68] R. Frucht and F. Harary, On the corona of two graphs, Aequationes Mathematicae 4 (1970) 322?324. [69] D. Gale, H. W. Kuhn, and A. W. Tucker, Linear programming and the theory of games, in Activity Analysis of Production and Allocation?proceedings of a conference, Wiley (1951) 317?329. [70] L. Y. Glebsky and G. Salazar, The crossing number of Cm ?Cn is as conjectured for n ? m(m + 1), Journal of Graph Theory 47 (2004) 53?72. [71] J. Gimbel, M. Mah?eo, and C. Viroulet, Double total domination of graphs, Discrete Mathematics 165/166 (1997) 343?351. [72] W. Goddard and M. A. Henning, Real and integer domination in graphs, Discrete Mathematics 199 (1999) 61?75. [73] W. Goddard, O. R. Oellermann, P. J. Salter, and H. C. Swart, Bounds on the total redundance and e?ciency of a graph, Ars Combinatoria 54 (2000) 129-138. [74] C. D. Godsil, Compact graphs and equitable partitons, Linear Algebra and its Appli- cations 255 (1997) 259?266. [75] C. D. Godsil and G. Royle, Algebraic Graph Theory, Springer, New York, NY, 2000. [76] R. J. Gould, T. suppressLuczak, and F. Pfender, Pancyclicity of 3?connected graphs: pairs of forbidden subgraphs, Journal of Graph Theory 47 (2004) 183?202. [77] S. Gravier, Total domination of grid graphs, Discrete Applied Mathematics 121 (2002) 119?128. [78] S. Gravier and M. Mollard, on domination numbers of Cartesian product of paths, Discrete Applied Mathematics 80 (1997) 247?250. [79] D. L. Grinstead and P.J. Slater, On the minimum intersection of minimum dominating sets in series-parallel graphs, in Y. Alavi, G. Chartrand, O. R. Oellermann and A. J. Schwenk (Eds.), Graph Theory, Combinatorics, and Applications, Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, vol. 1, pages 563?584, (Kalamazoo, MI 1988), Wiley Publications, 1991. 108 [80] D. L. Grinstead and P.J. Slater, Fractional domination and fractional packing in graphs, Congressus Numerantium 71 (1990) 153?172. [81] R. Grone, Private communication (2005). [82] J. L. Gross and J. Yellen (Eds.), Handbook of Graph Theory, CRC Press, New York, NY, 2003. [83] G. Gunther, B. Hartnell, L.R. Markus, and D. F. Rall, Graphs with unique minimum dominating sets, Congressus Numerantium 101 (1994) 55?63. [84] F. Harary and T. W. Haynes, Nordhaus?Gaddum inequalities for domination in graphs, Discrete Mathematics 155 (1996) 99?105. [85] F. Harary and T. W. Haynes, Double domination in graphs, Ars Combinatoria 55 (2000) 201?213. [86] F. Harary, T. W. Haynes, and P. J. Slater, E?cient and excess domination in graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 26 (1998) 83? 95. [87] F. Harary, A. J. Schwenk, Which graphs have integral spectra?, in: R. A. Bari, F. Harary (Eds.), Graphs and Combinatorics, Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University, June 18-22, 1973, Springer, Berlin (1974) 45?51. [88] E. O. Hare, k-weight domination and fractional domination of Pm ?Pn, Congressus Numerantium 78 (1990) 71?80. [89] E. O. Hare, Fibonacci numbers and fractional domination of Pm ? Pn, Fibonacci Quarterly 32 (1994) 69?73. [90] E. O. Hare and L. S. Stewart, Fractional domination of Pm?Pn, Congressus Numer- antium 91 (1992) 35?42. [91] D. J. Hart?el, Stochastic eigenvectors for qualitative stochastic matrices, Discrete Mathematics 43 (1983) 191?197. [92] J. H. Hattingh and M. A. Henning, Characterizations of trees with equal domination parameters, Journal of Graph Theory 34 (2000) 142?153. [93] J. H. Hattingh, M. A. Henning, P. J. Slater, Three?valued k?neighborhood domina- tion in graphs, Australasian Journal of Combinatorics 9 (1994) 233?242. [94] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998. [95] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (Eds.), Domination in graphs: Advanced Topics, Marcel Dekker, Inc., New York, 1998. [96] T. W. Haynes and M. A. Henning, Changing and unchanging domination: a classi?- cation, Discrete Mathematics 272 (2003) 65?79. 109 [97] S. M. Hedetniemi, S. T. Hedetniemi, and D. F. Rall, Acyclic domination, Discrete Mathematics 222 (2000) 151?165. [98] S. T. Hedetniemi, private communication (2005). [99] S. T. Hedetniemi and M. A. Henning, Defending the Roman Empire-A new strategy, Discrete Mathematics 266 (2003) 239?251. [100] S. T. Hedetniemi and R. C. Laskar, Recent results and open problems in domina- tion theory, in R. D. Ringeisen and F. S. Roberts (Eds.) Applications of Discrete Mathematics, pages 205?218, SIAM, Philadelphia, PA, 1988. [101] S. T. Hedetniemi and R. C. Laskar, Introduction (to an entire volume on domination), Discrete Mathematics 86 (1990) 3?9. [102] S. M. Hedetniemi, S. T. Hedetniemi, and T. V. Wimer, Linear time resource allocation algorithms for trees, Technical Report URI-014, Dept. of Math., Clemson University (1987). [103] M. A. Henning, Domination in regular graphs, Ars Combinatoria 43 (1996) 263?271. [104] M. A. Henning, Graphs with large total domination number, Journal of Graph Theory 35 (2000) 21?45. [105] M. A. Henning, A characterization of Roman trees, Discussiones Mathematicae Graph Theory 22 (2) (2002) 325?334. [106] M. A. Henning, Defending the Roman Empire from multiple attacks, Discrete Math- ematics 271 (2003) 101?115. [107] M. A. Henning, Signed total domination in graphs, Discrete Mathematics 278 (2004) 109?125. [108] M. A. Henning, Restricted total domination in graphs, Discrete Mathematics 289 (2004) 25?44. [109] A. J. W. Hilton, R. Rado, S. H. Scott, A (< 5)-colour theorem for planar graphs, Bulletin of the London Mathematical Society 5 (1973), 302?306. [110] A. J. Ho?man, A. W. Kolen, and M. Sakarovitch, Totally balanced and greedy ma- trices, SIAM Journal of Algebraic Discrete Methods 6 (1984) 721?730. [111] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, New York, NY, 1990. [112] R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, New York, NY, 1990. [113] S. B. Horton, C. N. Meneses, A. Mukherjee, and M. E. Ulu?cakli, A computational study of the broadcast domination problem, DIMACS Technical Report 2004?45 (2004) 1?8. 110 [114] W. Imrich, S. Klav?zar, Product Graphs: Structure and Recognition, Wiley- Interscience, New York, 2000. [115] M.S. Jacobson and L.F. Kinch, On the domination number of products of graphs I, Ars Combinatoria 18 (1983) 33-44. [116] M.S. Jacobson and L.F. Kinch, On the domination number of products of graphs II: trees, Journal of Graph Thoery 10 (1986) 97-106. [117] M.S. Jacobson, G. M. Levin , and E. R. Scheinerman, On fractional Ramsey numbers, Discrete Mathematics 176 (1997) 159?175. [118] C. F. de Jaenisch, Applications de l?Analyse Mathematique au Jue des Echecs, Pet- rograd (1862). [119] P. D. Johnson, R. R. Rubalcaba, and M. Walsh, Concerning fractional automorphisms, Congressus Numerantium 159 (2002) 113?117. [120] P. D. Johnson, R. R. Rubalcaba, and M. Walsh, The actions of fractional automor- phisms, Journal of Combinatorial Mathematics and Combinatorial Computing 50 (2004) 57?64. [121] P. D. Johnson, R. R. Rubalcaba, and M. Walsh, Domination null and packing null vertices of a graph, Congressus Numerantium, 168 (2004) 49?63. [122] P. D. Johnson, R. R. Rubalcaba, and M. Walsh, Fuzzi?cation and its discontents: a case study, submitted. [123] T. W. Johnson and P. J. Slater, Maximum independent, minimally redundant sets in series-parallel graphs, Quaestiones Mathematiae 16 (1993) 351?370. [124] A. Khodkar, S. M. Sheikholeslami, and H. Hasanzadeh, Bounds on double domination numbers of graphs, submitted. [125] S. Klav?zar and H.-G. Yeh, On the fractional chromatic number, the chromatic number, and graph products, Discrete Mathematics 247 (2002) 235?242. [126] S. Klav?zar and N. Seifter, Dominating Cartesian products of cycles, Discrete Applied Mathematics 59 (1995) 129?136. [127] A. Klobu?car, Domination numbers of cardinal products, Mathematica Slovaca 49 (1999) 387?402. [128] K. M. Koh, B. B. Lim, and P. J. Slater, H?domination in graphs, Discrete Mathe- matics 272 (2003) 97?105. [129] D.L. Kreher and W. Kocay, Graphs, Algorithms and Optimization, CRC Press, New York, NY, 2004. [130] M. Larsen, J. Propp, and D. Ullman, The fractional chromatic number of Mycielski?s graphs, Journal of Graph Theory 19 (1995) 411?416. 111 [131] J. B. Lasserre, Generating functions and duality for integer programs, Discrete Opti- mization 1 (2004) 167?187. [132] C. L. Lu, S. L. Peng, C. Y. Tang, E?cient minus and signed domination in graphs, Theoretical Computer Science 301 (2003) 381?397. [133] E. N. Luttwak, The grand strategy of the Roman Empire, John Hopkins University Press, Baltimore, MD, 1976. [134] A. Majumdar, Neighborhood hypergraphs: a framework for covering and packing parameters in graphs, Ph.D. Thesis, Clemson University, 1991. [135] J. D. Masters, Q. F. Stout, and D. M. Van Wieren, Unique domination in cross? product graphs, Congressus Numerantium, 118 (1996) 49?71. [136] B. D. McKay, Practical graph isomorphism, Congressus Numerantium 30 (1981) 45? 87. [137] A. Meir and J. W. Moon, Relations between packing and covering numbers of a tree, Pacific Journal of Mathematics 61 (1975) 225?233. [138] D. Michalak, Domination, independence and irredundance with respect to additive induced?hereditary properties, Discrete Mathematics 286 (2004) 141?146. [139] J. Mycielski, Sur le coloriage des graphes, Colloquium Mathematicum 3 (1955) 161? 162. [140] T. Nagoya, S. Toda, and R. Uehara, Graph isomorphism completeness for chordal bipartite and strongly chordal graphs, Discrete Applied Mathematics 145 (2005) 479? 482. [141] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, NY, 1999. [142] R. J. Nowakowski and D. F. Rall, Associative graph products and their indepen- dence, domination and coloring numbers, Discussiones Mathematicae Graph Theory 16 (1996) 53?79. [143] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications Inc., Mineola, NY, 1998. [144] J. B. Phillips and P. J. Slater, On the maximum in?uence of a maximal packing, Journal of Combinatorial Mathematics and Combinatorial Computing 33 (2000) 275? 288. [145] I. Peterson, Defending the Roman Empire, MAA online (available online only), (2000) http://www.maa.org/mathland/mathtrek 9 11 00.html [146] M. Ramada, E. R. Scheinerman, and D. H. Ullman, Fractional isomorphisms of graphs, Discrete Mathematics. 132 (1994) 247?265. 112 [147] R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford University Press, New York, 1998. [148] C. S. ReVelle, Facility siting and integer-friendly programming, European Journal of Operational Research 65 (1993) 147?158. [149] C. S. ReVelle, Can you protect the Roman Empire?, John Hopkins Magazine 49 (2) (1997) p. 40. [150] C. S. ReVelle, Test Your Solution to ?Can You Protect the Roman Empire?? John Hopkins Magazine 49 (3) (1997) p. 70. [151] C. S. ReVelle, Solving the Roman Legions Problem, John Hopkins Magazine 49 (4) (1997) (available online only) http://www.jhu.edu/?jhumag/0997web/roman.html [152] C. S. ReVelle and K. E. Rosing, Defendens Imperium Romanum: A classical problem in military strategy, American Mathematical Monthly 107 (7) (2000) 585?594. [153] R. R. Rubalcaba and M. Walsh, Minimum fractional dominating and maximum frac- tional packing functions, submitted. [154] R. R. Rubalcaba and M. Walsh, Fractional isomorphism invariants, in preparation. [155] L. A. Sanchis, Bounds related to domination in graphs with minimum degree two, Journal of Graph Theory 25 (1997) 139?152. [156] E. Sampathkumar, H. B. Walikar, The connected domination number of a graph, Journal of Mathematical Physics 13 (1979) 607?613. [157] E. R. Scheinerman and D. H. Ullman, Fractional Graph Theory, Wiley-Interscience, New York, 1997. [158] A. Schrijver, Theory of Linear and Integer Programming, Wiley-Interscience, New York, NY, 1986. [159] S. H. Scott, Multiple node colourings of ?nite graphs, Ph.D. Thesis, University of Reading, (1975). [160] W. J. Selig and P. J. Slater, Minimum dominating, optimally independent vertex sets in graphs, in Y. Alavi, G. Chartrand, O. R. Oellermann and A. J. Schwenk (Eds.), Graph Theory, Combinatorics, and Applications, Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, vol. 2, pages 1061?1073, (Kalamazoo, MI 1988), Wiley Publications, 1991. [161] P.J. Slater, Closed neighborhood order domination and packing, Congressus Numer- antium 97 (1993) 33?43. [162] P. J. Slater, Packing into closed neighborhoods, Bulletin of the Institute of Combina- torics and its Applications 13 (1995) 23?34. [163] P. J. Slater, Generalized graph parameters: Gallai theorems I, Bulletin of the Institute of Combinatorics and its Applications 17 (1996) 27?37. 113 [164] P. J. Slater, LP-duality, complementarity, and generality of graphical subset param- eters, in T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (Eds.), Domination in graphs: Advanced Topics, chapter 1, Marcel Dekker, Inc., New York, 1998. [165] P.J. Slater, private communication (2005). [166] P. J. Slater and E. L. Trees, A matrix partition linear programming theorem, Bulletin of the Institute of Combinatorics and its Applications 28 (2000) 75?84. [167] P. J. Slater and E. L. Trees, Multi?fractional domination, Journal of Combinatorial Mathematics and Combinatorial Computing 40 (2002) 171?181. [168] C. B. Smart and P. J. Slater, Complexity results for closed neighborhood order pa- rameters, Congressus Numerantium 112 (1995) 83?96. [169] J. P. Spinrad, E?cient Graph Representations, American Mathematical Society, Prov- idence, RI, 2003. [170] I. Stewart, Defend the Roman Empire!, Scientific American 281 (6) (1999) 136?139. [171] H. A. Taha, Integer Programming?theory, applications, and computations, Academic Press, New York, NY, 1975. [172] G. Tinhofer, Graph isomorphism and theorems of Birkho? type, Computing. 36 (1986) 285?300. [173] G. Tinhofer, A note on compact graphs, Discrete Applied Mathematics 30 (1991) 253?264. [174] D. H. Ullman, private communication (2005). [175] L. N. Vaserstein, Introduction to Linear Programming, Prentice Hall, Upper Saddle River, NJ, 2003. [176] W. D. Wallis, A Beginner?s Guide to Graph Theory, Birkh?auser, Boston, MA, 2000. [177] M. Walsh, private communication (2003-2005). [178] D. B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, NJ, 2001. [179] M. Wo?zniak, Packing of graphs and permutations?a survey, Discrete Mathematics 276 (2004) 379-391. [180] B. Yu, Convexity of minimal total dominating functions in graphs, Journal of Graph Theory 24 (1995) 313?321. [181] I. E. Zverovich and V. E. Zverovich, A semi-induced subgraph characterization of upper domination perfect graphs, Journal of Graph Theory 31 (1999) 29?49. 114 Appendix A Notation Symbol Meaning Page: A(G) adjacency matrix 3 A(C) cell adjacency matrix 28 Aut(G) automorphism group 25 B vertex?edge incidence matrix 3 Cn cycle on n vertices 2 d(v) degree of a vertex v 2 d(u,S) number of edges from u to a set S of vertices 27 dd double domination number 5 DG set of all MFDFs on G 40 D?G set of all MFTDFs on G 68 E(G) edge set of a graph 2 F e?cient domination number 8 Ff fractional e?cient domination number 8 FDPF fractional dominating-packing function 39 FDT-OPF fractional total dominating?open packing function 67 MFDF minimum fractional dominating function 6 MFPF maximum fractional packing function 7 MFTDF minimum fractional total dominating function 8 MFOPF maximum fractional open packing function 9 115 Symbol Meaning Page: n order 2 N neighborhood matrix, A + I 3 N[u] closed neighborhood of a vertex v 4 N(u) open neighborhood of a vertex v 4 Pn path on n vertices 2 PG set of all MFPFs on G 40 P?G set of all MFOPFs on G 68 S ? V set of vertices 4 V vertex set of a graph 2 ?f fractional independence number 25 ? upper domination number 8 ? domination number. 6 ?c connected domination number 100 ?f fractional domination number 6 ?k k-domination number 5 ?r weak Roman domination number 101 ?{k} {k}-domination number 99 ?res restrained domination number 100 ?R Roman domination number 85 ?R?f fractional (open) Roman domination number 87 ?Rf fractional (closed) Roman domination number 91 ?t total domination number 8 ??f fractional total domination number 8 116 Symbol Meaning Page: ? maximum vertex degree 2 ? minimum vertex degree 2 ? number of edges 2 ? matching number 9 ?f fractional matching number 9 ? crossing number 25 ? (closed neighborhood) packing number 7 ?t open (neighborhood) packing number 9 ??R (open neighborhood) beamer?bu?er number 88 ?R (closed neighborhood) beamer?bu?er number 92 ? chromatic number 119 ?f fractional chromatic number 25 ?? edge chromatic number 119 ? clique number 119 f the vector vectorf 6 f|H The function f restricted to the subgraph H 51 ?G complement 34 [G] partial generalized Haj?os graph formed from G 17 G[H] The induced subgraph H ? V 4 Gm,n m?n grid graph 15 117 Symbol Meaning Page: GsquareH Cartesian product of G and H 14 G?H categorical product of G and H 14 G?H strong direct product of G and H 14 G?H disjoint union of G and H 14 G?H corona of G and H 15 G ?= H Graphs G and H are isomorphic 19 G ?=? H Graphs G and H are semi?isomorphic 37 G ?=f H Graphs G and H are fractionally isomorphic 20 [Kn] generalized Haj?os graph 16 Kn The complete graph; also know as a clique on n vertices 43 K?1,t Healthy spider 44 T(Kn) trampoline on 2n vertices 16 TH(G) partial trampoline formed from Hamiltonian cycle H 16 x?y tensor product of the vectors x and y 54 Y (G) Mycielski of a graph G 15 118 Appendix B Non?Invariants of Fractional Isomorphisms |Aut| = |D3 ?D4| = 48|Aut| = |D7| = 14 Figure 1: Size of automorphism groups. ? = 3 ? = 2 Figure 2: Independent sets of maximum size. 119 ? = 2 ? = 3 Figure 3: Minimum proper colorings. ?? = 3?? = 2 Figure 4: Minimum proper edge colorings. ? = 2 ? = 3 Figure 5: Largest induced cliques. ? = 3 ? = 2 Figure 6: Maximum matchings. 120 ? = 1? = 0 Figure 7: C6 and C3 ?C3 drawn with minimum number of edge crossings in the plane. ?f = 2 C6 C3 ?C3 ?f = 2 ?f = 3 ?f = 3 Figure 8: Fractional chromatic number, fractional clique number, and fractional indepen- dence number. ? = 4? = 3 Figure 9: Minimum dominating sets. 121 ?t = 5 ?t = 6 Figure 10: Minimum total dominating sets. ?res = 3 ?res = 5 Figure 11: Minimum restrained dominating sets. ?2 = 3 ?2 = 4 Figure 12: Minimum 2-dominating sets. 122 dd = 6 dd = 7 Figure 13: Minimum double dominating sets. ?R = 7?R = 6 Figure 14: Minimum Roman dominating functions. ? = 3 ? = 2 Figure 15: Maximum minimal dominating sets. 123 F = 6F = 9 Figure 16: E?cient domination number. pi = 3 pi = 2 Figure 17: Maximum 2?packings (closed neighborhood packings). pit = 4 pit = 3 Figure 18: Maximum open neighborhood packings. 124 Appendix C Classification of Graphs With 5 or Fewer Vertices G30 G35 G43 Figure 19: Class N graphs on 5 or fewer vertices. G31 Figure 20: Class I graphs on 5 or fewer vertices. G14 G37G36 G41 G25 Figure 21: Class D graphs on 5 or fewer vertices. 125 G49 G21 G15G13G6 G10 G17 G24 G26 G27 G33 G42 G47 G50 G51 G46 G29 G34 G40 Figure 22: Class P graphs on 5 or fewer vertices. 126 G16 G38 G39G28 G44 G48 G52 G5 G1 G8 G3 G19 G20 G22 G23 G4 G9 G2 G7 G11 G12 G18 G32 Figure 23: Class E graphs on 5 or fewer vertices. 127