DIMACS DREI '99

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.

#### 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.

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.

Updated 07/21/99