Week 2 Topic:Concepts of Domination in Graphs and Directed Graphs
July 26 - 30, 1999
Abstracts
Janez Ales,
Simon Fraser University
Walecki tournaments
Lucas tournaments, today known as Walecki tournaments,
were defined by Alspach in 1966.
A mapping between cycles of the complementing circular
shift register and isomorphism classes of Walecki tournaments
was found.
A upper bound on the number of isomorphism
classes of Walecki tournaments
was determined.
Alspach conjectured that the bound is tight.
The problem of enumerating Walecki tournaments
has not been solved to date.
However, it was published as an open
problem in a paper by
Alspach, Bermond, and Sotteau in 1987,
and as a research problem by
Alspach in 1989.
In an attempt to prove this 33 years old conjecture we determine
the automorphism groups of Walecki
tournaments for all but those whose defining binary sequences
are aperiodic.
Techniques used in the proof originate from a
diverse range of topics:
permutation groups, tournaments, and
bijective enumeration,
to mention a few.
Michael F. Bridgland,
IDA Center for Computing Sciences
Serving no more than one master
Recently, Tom Potter and Jim Kraft developed a simple and surprising
nondeterministic asynchronous distributed spanning tree algorithm. In
rough outline, the algorithm imposes a total order on the vertices of a
connected graph G, then repeatedly selects an edge and moves it
(making it incident with a different pair of vertices) until the
resulting multigraph M is a tree with multiple edges. Finding a
spanning tree of M is easy: just delete multiple edges! The
resulting spanning tree of M is unlikely to be a subgraph of G;
however, moving its edges back to their original positions
in G produces a spanning tree of G.
Which spanning trees does the algorithm produce? In this talk, we
analyze the algorithm via a related problem on vertex dominance in
vertex-ordered loopless multigraphs. Write v \sin w if vertices v
and w are adjacent. For v,w in V, say that v dominates
w if there exist vertices v_1 > v_2 >... v_k in V
(with k >= 1) for which v = v_1 \sin v_2 \sin v_k = w.
Say that v is a master of w if
(i) v \sin w, (ii) v > w ,and
(iii) there does not exist a vertex x for which v
dominates x and x dominates w.
A single-master graph is a graph in which no vertex has more
than one master. Problem: Given an arbitrary graph G, add as few
edges as possible to form a single-master graph S(G). We establish
the existence and uniqueness (up to isomorphism) of S(G), and
use S(G) to characterize the spanning trees produced by the
Potter-Kraft algorithm. We also enumerate the isomorphism classes of
graphs S(G) without multiple edges in which each edge joins some vertex
to its master.
Robert Brigham,
University of Central Florida
Achievable sequences for domination invariants
A sequence a_1,a_2,...,a_n of nonnegative integers is achievable for invariant I if there is an associated sequence of graphs G_1, G_2,...,G_n, such that (1) G_i has i vertices for 1 <= i <= n, (2) G_i is an induced subgraph of G_{j+1} for 1<= i <= n - 1, and (3) I(G_i) = a_i for 1 <= i <= n. This talk summarizes what has been accomplished when I represents various types of domination and discusses current efforts when I refers to distance 2 domination.
W. Edwin Clark,
University of South Florida
Tight upper bounds for domination numbers of graphs of given order and minimum degree
I hope to interest some participants in the problem of determining the largest possible domination number for graphs with n vertices and minimum degree d. There are four values for (n,d) with n <= 16 that are still unknown.
Nate Dean,
Rice University
Solving Puzzles and Winning Games with Graphs
Life is filled with puzzles and with competitions or games
(for example, war, politics, romance, athletics, business,
and so on), and for any puzzle or game the ultimate outcome
depends on the strategies adopted by the players.
A solution or winning strategy is usually difficult, if not
impossible, to find.
This talk focuses on puzzles and two-player games without
chance to demonstrate how graph theory can be used to
analyze them, solve them, and win.
Faun Doherty,
University of Colorado at Denver
Chromatic number and planarity of domination-compliance graphs
Given an n-tournament T, two vertices x and y dominate T if together they beat all other vertices. The domination graph dom(T) of T is the graph on the vertex set of T with edges between vertices which dominate T. Two vertices x and y are a compliant pair if every other vertex in T beats either x or y. The compliance graph com(T) of T is the graph on the vertex set of T with edges between vertices which form a compliant pair. One can see that the relationship between dom(T) and com(T) is com(T) = dom(~T) where ~T is the reversal of T. The domination-compliance graph of T is dom(T) U com(T). The questions addressed here will be of the planarity and chromatic number of domination-compliance graphs. We shall determine that the chromatic number of most domination-compliance graphs is three, while some have chromatic number two. We shall identify the only family of tournaments whose domination-compliance graph contains a 4-clique. To answer these and other questions, we determine all possible edges of domination-compliance graphs given a domination (or compliance) graph. This characterization enables us to investigate whether or not all domination-compliance graphs are planar. We conjecture that they are.
Jean Dunbar,
Converse College
Domatically speaking for G and its complement
The maximum caxdinality of a partition of the vertex set of a graph G into dominating sets is the domatic number of G. Graphs G are examined for which G and its complement have equal domatic numbers. Characterizations of trees, cycles, and cubic graphs which have this property are given. Secondly, Nordhaus-Gaddum type bounds are given with characterizations of graphs achieving these bounds. Finally, more recent results currently in-process will be reported.
Ronald D. Dutton,
University of Central Florida
Invariant values from edge deleted subgraphs
Graphs with fewer than four edges are not uniquely reconstuctable from their edge deleted subgraphs. It is believed that these are the only exceptions to the general edge-reconstruction conjecture. Graphs in certain infinite classes are known to be edge-reconstuctable, for example, those with two or more nontrivial components, trees, and regular graphs. Also, graphs with a sufficient number of edges can be uniquely determined from the edge-deleted subgraphs. For example, any graph on p vertices and at least p(p-1)/4 > 3 edges 255 -better bounds are known- is edge-reconstuctable . Thus, for any graph with at least 4 edges, either it or it's complement is edge-reconstructable.
We can, though, for any graph with at least four edges, determine (recognize) certain invariant values or properties such as the number of vertices p, the number of edges E, the degree sequence, connectedness, and whether a graph is bipartite. In this paper, we show certain variants of the domination number of a graph are recognizable from the edge-deleted subgraphs.
Stephen Finbow,
Dalhousie University
Fire fighting: an application of domination
Three years ago, the following problem was introduced at a conference at the University of Manitoba. Fires start at F nodes of a graph and then the local fire department deploys D defenders (fire fighters) to "protect" D nodes not yet on fire. Then the fires spread to any neighboring nodes not previously protected. The fires and the fire department take turns until the fires can spread no longer. We shall examine two cases: when the fires start on a random set of nodes and when they start at the set of nodes which maximizes the damage to the graph.
David Fisher,
University of Colorado
Large domination problems on rectangular chessboards
A (k*n) chessboard is dominated if each square either has a piece
on it or attacking it. Can you dominate a (5*12) board with 8 Kings
(easy)? 4 Queens (hard)? 10 Bishops (hard)? 10 Knights (very hard)? Or 5 Rooks
(very easy)? The (k*n) King (resp., Queen, Bishop, Knight, or
Rook) domination number is the least number of Kings (resp., Queens,
Bishops, Knights, or Rooks) which can dominate a (k*n) board.
(1)We show that the k*n King domination number is \lceil k13 \rceil \lceil n13 \rceil.
(2)We find the k*n Queen domination number for k <=10 and for all n wih a sophisticated exhaustive search.
(3)We find the k*n Bishop domination number if n/2 <= k <= 2n (with Paul Thalos).
(4)We find the k*n Knight domination number for k <= 10 and for all n (with Ann Spalding).
(5)We show the k*n Rook domination number is (k,n).
Gerd Fricke,
Wright State University
Frational parameters of graphs
We will discuss the frational version of domination and irredundance and give several simple results.
Hortensia Galeana-Sanchez,
Universidad Nacional Autonoma de Mexico
Kernels by monochromatic paths
In this talk the concepts of kernel by monochromatic paths is introduced,
an application to decision problems and a survey on results about the existence of kernels by monchromatic paths.
Jerrold W. Grossman,
Oakland University
Using graph theory to study research collaboration
Joint work with Patrick D. F. Ion
Let C be the collaboration graph of mathematical researchers. Specifically, the vertices of C are all people who have published items that appear in the database of Mathematical Reviews (which includes most research books and papers in mathematics published since 1940), and there is an edge between vertices u and v if u and v have published one or more joint items (with or without other co-authors). Although the data we have is not totally accurate (primarily because of the problem of identifying authors as people rather than as strings of characters appearing on a paper's by-line), it appears that C has (very roughly) about 400,000 vertices and 1,000,000 edges.
We have begun a long-term project of using graph theoretical and statistical techniques to shed some light on C and thereby deduce some nontrivial statements about the nature of mathematical research collaboration. Of course, since the graph is so large, exact computation of parameters such as dominating number may not be feasible P = NP. The talk will discuss some of our preliminary findings. This project grew out of the notion in mathematical folklore of Erdos number, inspired by the fact that Paul Erdos (1913--1996) had nearly 500 collaborators. (A person's Erdos number is the distance between that person and Erdos in-C.) The talk will touch briefly on some of the interesting aspects of this notion and the man at its center.
Dave Guichard,
Whitman College
Domination graphs of tournaments, Part 2
Given a tournament T, we say vertices x and y dominate T if
and only if for every other vertex z, (x,z) or (y,z) is an arc
in T. The domination graph of T, dom(T), is the
graph on the vertices of T with edge {x,y} if and only if x
and y dominate T. We complete the characterization of domination
graphs of tournaments by describing exactly which graphs with more
than one connected component are such graphs.
Gregory Gutin,
Brunel University
When does a multipartite tournament have a King?
A multipartite tournament is an orientation of a complete multipartite graph. A vertex v of a digraph D is a k-king if the length of a shortest path from v to any other vertex of D does not exceed k. It is well-known that every tournament has a 2-king. No multipartite tournament with at least two vertices of in-degree zero has a k-king (k is finite). Gutin (1986) and, independently, Petrovic and Thomassen (1991) proved that every multipartite tournament with at most one vertex of in-degree zero has a 4-king. We will consider schemes of various proofs of this theorem and look at some related results.
Bert Hartnell,
Saint Mary's University
Domination in cartesian products and Vizing's Conjecture
Part II: Some recent results
As explained in the previous talk on this topic, 2-packings have long been recognized as playing a useful role in obtaining a lower bound for the domination number of the Cartesian product of two graphs. Here we will outline more recent attempts to exploit the nature of 2-packings more fully to establish improved lower bounds.
Teresa Haynes,
East Tennessee State University
Frameworks for Domination
Joint work with Chartrand, Henning, and Zhang
Motivated by numerous applications, many domination parameters
have been defined and investigated. In general, each of these
parameters has been studied independently of the others. In
Chapter 11 of Fundamentals of Domination in Graphs, the
authors identify several mathematical ``frameworks'', each of which
provides a unifying theory into which many of these parameters fit.
Each such frameworkprovides a mathematical viewpoint that enables one to
identify common properties of known and new parameters, see theoretical relationships among many of these parameters, and develop insight into the computational complexity issues of the problems involving these graphical parameters.
For example, viewing these problems from a framework perspective
provided a template algorithm for solving six similarly
formulated problems.
In the first part of this talk, we survey the frameworks given in
the previously mentioned chapter. Second a new framework
involving stratified graphs, affectionately called Color Me
Domination, is presented.
Stephen Hedetniemi,
Clemson University
An introduction to the theory of domination in graphs
I. Ore's Domination Theorem and its many generalizations.
Ore's Theorem is considered by many to be the first theorem
in domination theory. As simple as it is, it has quite
a few nice generalizations.
II. Gallai's Theorem as it relates to Domination.
This simple theorem has literally dozens and dozens
of generalizations, including quite a few in domination
theory.
III. The Domination Inequality Chain
This inequality chain of six domination parameters
is easily one of the most central points of study in
domination theory, and at the same time is one of the
deepest.
IV. The first domination algorithm
This simple algorithm for trees was the precursor to
quite a few domination algorithms of a similar nature.
Each of these four sections begins with a really simple
result, that anyone can understand, almost immediately.
But, as expected, each gets deeper and deeper the more
you look into it. Each section concludes with some
nice open problems and avenues for exploration.
Michael Henning,
University of Natal
Domination in planar graphs with small diameter
Joint work with Wayne Goddard
MacGillivray and Seyffarth (Domination numbers of planar graphs, J. Graph Theory 22 (1996), 213--229) proved that planar graphs of diameter two have domination number at most three and planar graphs of diameter three have domination number at most ten. They also give examples of planar graphs of diameter four, and nonplanar graphs of diameter two, having arbitrarily large domination numbers. In this talk, we improve the results of MacGillivray and Seyffarth. We show that there is a unique planar graph of diameter two with domination number three. Hence every planar graph of diameter two, different from this unique planar graph, has domination number at most two. We prove that every planar graph of diameter three and of radius two has domination number at most six. We then show that every planar graph of diameter three has domination number asymptotically at most six.
Suh-Ryung Kim,
Kyung Hee University
Competition graphs and its variants
The competition graph of a digraph D is the graph on the same vertices as D with an edge between two vertices if they beat a common vertex in D. The competition graph of a digraph is the complement of the domination graph of its reversal. Competition graphs were introduced by Cohen in 1968 as a means of determining the smallest dimension of ecological phase space. Various notions analogous to competition graphs together with competition graphs have applications, not only to ecology, but in studying communication over a noisy channel, in assigning frequencies to radio transmitters, and in modeling complex economic and energy systems. In this talk, we survey the results about the competition graph and some of its variants, namely, the competition-common enemy graph, the niche graph, the p-competition graph, and the m-step competition graph.
Khee Meng Koh,
National University of Singapore
How many kings does a multipartite tournament have ?
Landau (1953) showed that every tournament contains
a 2-king. Gutin (1986) and, independently, Petrovic and
Thomassen (1991) showed that if T is a multipartite tournament
containing at most one transmitter, then T contains a 4-king.
Obviously, T contains exactly one 4-king if T contains a unique
transmitter. A question arises natually. Suppose T contains no
transmitters. What is the least possible number of 4-kings that T
can have ? In this talk, we shall begin with a discussion on a
solution to this question, and proceed to introduce some recent
results in this area, including Gutin and Yeo's result on kings in
semicomplete multipartite digraphs.
Renu Laskar,
Clemson University
Domination and related topics in digraphs
Joint work with J.Ghoshal and D. Pillone
Domination and other related concepts in undirected graphs are well
studied ,
however,the respective analogs on digraphs have not received much
attention.
We present results concerning domination , kernels and solutions in
digraphs
along with some applications in game theory.
Lisa Markus,
De Anza College
Gallai-type Theorems and Domination Parameters
Joint work with G.S. Domke and J.E. Dunbar
A longstanding upper bound for the domination number is n-delta(G). For
the upper domination number, an upper bound is n-delta(G). In this talk
I discuss graphs which achieve these upper bounds.
Alice McRae,
Appalachian State University
On finding dominating sets in graphs
Let P be some domination parameter of interest. A reasonable
question is how to find some largest or smallest property P set in a
graph. However, for most any property P, there are no known algorithms
for computing an optimal solution. Most of
these problems have been proven NP-hard, which likely means
that there will never be any polynomial-time algorithms for computing
them. One approach is to find a heuristic algorithm
that computes a good, though probably suboptimal, solution in
a reasonable amount of time. Ideally, this algorithm could approximate
an optimal solution within some small error bound.
This talk discusses known algorithms for approximating a few
domination-related parameters and shows that the task of approximating
a few others is as difficult as calculating an optimal solution.
Sara Merz,
Reed College
Domination graphs of tournaments, Part 1.
Given an n-tournament T, we say vertices x and y dominate T if
for every other vertex z, (x,z) or (y,z) is an arc in T. The domination
graph of T, dom(T), is the graph on the vertices of T so that {x,y} is an
edge iff x and y dominate T. A graph G is a domination graph if there is
a tournament T so that dom(T)=G. In this talk we discuss necessary
conditions for a graph to be a domination graph and sufficient conditions
for a connected graph to be a domination graph.
Douglas F. Rall,
Furman University
Domination in cartesian products and Vizing's Conjecture
Part I: An Introduction
A well-known problem in domination theory is the long standing conjecture of V.G. Vizing from 1963 that the domination number of the Cartesian product of two graphs is at least as large as the product of the domination numbers of the individual graphs. Although limited progress has been made this problem essentially remains open. In this introductory talk, a brief survey of progress will be outlined.
Domination in Cartesian Products and Vizing's Conjecture
K. Brooks Reid Chair,
California State University at San Marcos
Variations of domination in tournaments
We will present a brief introduction to tournaments and their applications
followed by a discussion of several variations of domination in
tournaments. We will discuss, among other things, 1-step domination
(i.e., ordinary domination), Schutte's Property, {1, 2}-step domination
(i.e., kings), monochromatic domination, and domination pairs and
domination graphs. Several open problems will be described.
Fred Roberts Program Director,
DIMACS, Rutgers University
The One-Way Street Problem
Motivated by the desire to make traffic move more efficiently, we
sometimes seek to make every street in a traffic network one-way.
This leads to the problem of finding a strongly connected orientation
of a graph, an assignment of a direction to each edge of the graph so
that in the resulting directed graph, every point can reach every
other point by a directed path. This problem is 60 years old and has
led to a large amount of very interesting mathematics. The problem is
characterized by the fact that approaches to it are readily accessible
at an elementary level, but after a short time even an audience with
no background in graph theory can be led to the frontiers of research.
Moreover, this problem is characterized by the fact that it
illustrates many of the most important modern themes in discrete
mathematics: Mathematical models, graph structures, algorithms, etc.
This talk will describe both historically important results on
the one-way street problem and some recent work. While there
is a nice characterization of graphs which have strongly connected
orientations and there are even very good algorithms for finding
strongly connected orientations if they exist, the problem of finding
a most efficient strongly connected orientation, in any of several
senses of efficient, is in general difficult in a sense to be made
precise. Recent results show how to find optimally efficient strongly
connected orientations for grid graphs which arise in traditional
city-street networks and annular cities with circular beltways, and these
will be described.
Li Sheng,
Drexel University
Competition Graphs and Phylogeny Graphs
Motivated by problems of phylogenetic tree reconstruction, we
introduce notions of phylogeny graph and phylogeny number. These
notions are analogous to and can be considered as natural
generalizations of notions of competition graph and competition number
that arise from problems of ecology. In this talk, we describe
results about phylogeny number analogous to a number of well-known
results about competition number. In particular, we show that the
computation of phylogeny number is NP-complete and we calculate the
phylogeny number for triangulated graphs, line graphs, and graphs with
zero, one, or two triangles. We also give an upper bound for phylogeny
number of a graph with $n$ vertices.
Peter Slater,
University of Alabama at Huntsville
Duality and complementarity, graphical functions and y-valued parameters
Graph theoretic subset (that is, {0,1}) problems such as dominating
set, enclaveless set, packing, covering and independent set have their
"fractional" [0,1]-valued variants. More generally, we can consider the
Y-valued versions of these problems for an arbitrary set Y of real
numbers. Graphical subset problems will be discussed within the framework
of Y-duality and the fairly recently introduced Y-complementarity.
Most of the well-studied domination-related parameters, for example,
fit within this framework. As well, many as yet unstudied (or minimally
considered) interesting parameters are defined within the
duality/complementarity structure. Hence, many interesting open problems
abound.
Anne Spalding,
Mesa State College
Solving domination problems using min-plus algebra
Min-Plus Algebra is an algebra on the real numbers using
minimization and addition. It is used to simplify the
implementation of dynamic programming algorithms for finding
the domination number of the following types of graphs.
Complete Grid Graphs: P_n*P_r are the cartesian product of
two paths on n, r nodes respectively. We find the domination number
of P_n* P_r for n 19 and all r.
Cartesian Product Graphs: G* P_r with G being any graph
on n \le 6 nodes and P_r being a path on r nodes. We find
the domination number of G* P_r for all r.
Circulant Graphs: C_r[S] with [S] being a subset of {1,2,...9} is a graph on vertices 0,1,...r-1 with vertex i adjacent to
j if i-j is in S or j-i is in S (mod r). We find the domination
number C_r[S] for all r.
In addition to finding the domination numbers of the above graphs,
we will show how Min-Plus algebra and dynamic programming algorithms can be
implemented to solve a variety of other problems.
David Sumner,
University of South Carolina
Domination critical graphs
If a graph-theoretic property is worth studying, then it
is worthwhile to investigate those graphs that are
critical or minimal with respect to that property. Such
graphs may be central to inductive arguments and/or may
provide insight into a property's fundamental nature.
In the case of the domination number, there are many
choices for what should constitute a critical graph. One
could choose to study those graphs whose domination
number decreases whenever an edge is added, or increases
whenever an edge is deleted, or decreases whenever a
vertex is removed, and so on. A great deal of work has
been done in recent years on these and related concepts.
This talk will survey what is known and unknown about
these ideas.
Eric Trees,
University of Alabama at Huntsville
An LP matrix partition theorem and multi-fractional domination
Many graph theoretic subset parameters, such as, fractional domination,
fractional independence, and fractional packing, can be formulated as Linear
Programming (LP) problems, where the constraint matrix for the LP-problem
is the
closed neighborhood, adjacency, incidence, or total matrix. The Automorphism
Class Theorem (ACT) states that there exists an optimum LP-solution which is
constant on automorphism classes. We investigate the properties of the
constraint matrix, which allow for this constant solution. The property that
results is referred to as the Partition Class Theorem (PCT). We show that the
PCT is a generalization of the ACT.
As an extension of the fractional domination and fractional domatic
graphical parameters, multi-fractional domination is introduced. We will
demonstrate its LP-formulation, and to this formulation we apply the PCT. We
investigate some properties of the multi-fractional domination number and its
relationship to the fractional domination and fractional domatic numbers.
Lucas van der Merwe,
East Tennessee State University
Total domination edge critical graphs with minimum diameter
Denote the total domination number of a graph G by gamma_t(G).
A graph G is said to be total domination edge critical, or simply
gamma_t-critical, if gamma_t(G+e)< gamma_t(G) for each edge
e in the complement of G) . For 3_t-critical graphs G, that is, gamma_t-critical
graphs with gamma_t(G) =3, the diameter of G is either 2 or 3. We
study the 3_t-critical graphs G with (G) = 2.
Anders Yeo,
University of Victoria
Polynomial algorithms for the traveling salesman problem
Let V(D) be the vertex set of a digraph D and let A(D) be the arc set of D. A complete digraph of order n is a digraph where the arcs xy and yx both lie in A(D), for all x,y in V(D) x < > y and |V(D)|=n. A Hamilton cycle in a digraph D is a directed cycle containing all vertices exactly once.
One of the best-known problems in combinatorial optimization and algorithmics is the Travelling Salesman Problem (TSP). The most general form of the TSP is the directed version, where we want to find a minimum cost Hamiltonian cycle in a complete digraph, where costs are assigned to the arcs. It is well-known that the TSP is NP-complete, which implies that we are unlikely to find a polynomial algorithm, which can solve this problem exactly.
Let D_n be a complete digraph of order n, with costs assigned to its arcs, and let H be any Hamilton cycle in D_n. The domination number of H is defined to be the number of distinct Hamilton cycles in D_n, which have cost greater than or equal to the cost of H.
We state several conjectures and results culminating in the fact that we in polynomial time can find a Hamilton cycle of any D-n, such that the domination number of our solution is at least (n-1)!/2 (based on an unpublished result by Haggkvist. As there are only (n-1)! distinct Hamilton cycles in D, clearly (n-1)!/2 is half of all Hamilton cycles. Our result proves a conjecture by Glover and Punnen (1997). The above algorithm is not practical, but we will also state a practical algorithm, with domination number (n-2)! (based only on published results).
The TSP is a special case of the more difficult Quadratic Assignment Problem (QAP). Our polynomial method also works for the QAP, but we can only prove the (n-2)! bound when n is a prime. For general n we can prove the bound Omega(n!/k^n) for any k>1. This is however the first method for the QAP, which gives exponential domination numbers (for polynomial algorithms). Contrary to the TSP, there didn't exist any algorithms for the QAP with more than a polynomial size domination number, prior to the above algorithm.
|