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