DIMACS DCI '00
Week 1 Topic: Graph Partitions
July 10 - 14, 2000

Abstracts



Lars Dovling Andersen, Aalborg University

Edge-colouring bipartite graphs without 2-coloured 4-cycles
Joint work with Eric Mendelsohn

It is well known that any bipartite graph of maximum degree d has an edge-colouring with d colours (a proper edge-colouring, i.e., edges incident with the same vertex have distinct colours). We have begun an investigation of when this can be done without 2-coloured 4-cycles being present.

So far, we have been particularly interested in bipartite graphs of maximum degree 3, so this is what most of the talk will be about.



Darryn Edward Bryant, University of Queensland

Very small embeddings of some partial Steiner triple systems

A Steiner triple system of order v is a partition of the edges of the complete graph on v vertices into triangles. A partial Steiner triple system of order v is a partition of some subset of the edges of the complete graph of order v into triangles. Not every partial Steiner triple system of order v can be completed to a Steiner triple system of order v, but it is known that any partial Steiner triple system can be completed to a Steiner triple system of larger order. Such completions are called embeddings of the partial Steiner triple systems. The Lindner conjecture states that any partial Steiner triple system of order u can be embedded in a Steiner triple system of order v whenever v is equivalent to 1 or 3 (mod 6) and v is at least 2u+1. Although in one sense this is the best possible result on the embedding problem, some partial triple systems of order u can be embedded in Steiner triple systems of order less than 2u+1. Such embeddings will be topic of this talk.



Michael Daven Mount Saint Mary College

Maximal sets of hamilton cycles in complete multipartite graphs

In a connected graph G, a set S of hamilton cycles is called maximal if G - S contains no hamilton cycle. The spectrum for maximal sets in G is the set of numbers m such that there is a maximal set of size m. The spectrum for complete graphs and complete bipartite graphs has been studied. We will look at complete multipartite graphs.



Jeffery H. Dinitz University of Vermont

Complimentary Steiner Triple Systems
Joint work with Esther Lamken and Alan Ling

A Steiner triple system of order v, STS(v), is a partition of the edges of the complete graph on v vertices into triangles (called blocks). It is well known that there are v(v-1)/6 blocks in a STS(v). In order to generate all the blocks using the cyclic group of order v, one therefore needs (v-1)/6 base blocks, these base blocks are called a (v,3,1)-difference family. We will first discuss when there exists a difference family in which all the blocks are disjoint.

An s-partial resolution of an STS is a partition of the blocks into partial parallel classes each containing s blocks. Hence the existence of a difference family with disoint blocks yields a (v-1)/6 - partial resolution of an STS(v). Two s-partial resolutions R and R' of an STS(v) are orthogonal if a partial parallel class in R and a partial parallel class in R' contain at most one block in common. In this case the blocks of the STS can be placed in a v x v square with exactly (v-1)/6 blocks in each row and each column and no symbol appearing twice in any row or column (i.e. each row and column is a (v-1)/6 - partial parallel class). From the numbers, one sees that it may be possible to place 6 STS(v) (on the same symbol set) in a v x v square such that only the diagonals are empty and each of these STS have the property that the each row and column is a (v-1)/6 - partial parallel class. It may even be possible that every symbol appears 3 times in all but one row and column (in which it does not appear at all); and that if the triples are ordered, the square can be decomposed into 3 mutually orthogonal latin squares of side v.

We will show that such a square exists for all v = 1 mod 6 with at most 10 exceptions.



Saad El-Zanati Illinois State University

On graph labelings and graph decompositions

Graph labelings were first introduced by Alex Rosa (around 1967) as means of attacking the problem of cyclically decomposing the complete graph into other graphs. Since Rosa's original article, literally hundreds of papers have been written on graph labelings (mostly on beta-labelings, also known as graceful labelings). Unfortunately however, most of these papers bare little relation to Rosa's original intent (investigating cyclic decompositions).

In this talk we will review some of the various graph labelings with a focus on their decomposition applications. The talk is accessible to both students and teachers of high-school level mathematics.



David Fisher University of Colorado at Denver

Fractional Domatic Numbers and Asymptotic Knight Density

A "Knight" in Chess attacks two squares horizontally or vertically, and then one square perpendicular. A set of Knights "cover" a board if a Knight attacks every empty square. What is the minimum number of Knights needed to cover an nxn board? This is the domination number of the nxn Knight graph: nodes (i,j) for all i,j=1,2,...,n and edges between node (i,j) and (k,l) if |i-k||j-l|=2.

A Knight covers at most 9 squares. So at least n^2/9 Knights are needed to cover an nxn board. However, the sparsest known Knight covers have density 1/8. What is the asymptotic density? Look at Fractional Domatic Number (FDN): a maximum fractional packing of a graph with dominations. We show the asymptotic sparsest density is the inverse of the FDN of the infinite Knight graph.

A dual solution to the FDN problem is a set of weights on the nodes whose sum in any domination is at least one. For example, consider these weights on the Knight graph (with denominator of 40). Outside, the weights are 0.

2 3 4 4 3 2

2 6 6 7 7 6 6 2

3 6 8 10 10 8 6 3

4 7 10 10 10 10 7 4

4 7 10 10 10 10 7 4

3 6 8 10 10 8 6 3

2 6 6 7 7 6 6 2

2 3 4 4 3 2

Any set of Knights covering the middle 4x4 lie on squares whose weights sum to at least 1. These weights add to 8.8. So the FDN of the infinite Knight graph is at most 8.8, and the asymptotic density of a Knight cover is at least 1/8.8 improving the best known lower bound of 1/9.

These techniques show promise for many asymptotic problems on regular graphs.



Chin-Mei Kau Fu Tamkang University

Cycle decompositions of the complete bipartite graph

A bipartite graph is one whose vertex set can be partitioned into two subsets X and Y, so that each edge has one end in X and one in Y; such a partition (X,Y) is called a bipartition of the graph. A complete bipartite graph is a simple bipartite graph with bipartition (X, Y) in which each vertex of X is joined to each vertex of Y. If |X| = m and |Y| = n, such a graph is denoted by Km,n. A 2-fold complete bipartite graph 2Km,n is a bipartite graph with bipartition (X, Y) in which each vertex of X is joined to each vertex of Y by exactly 2 edges. The problem of the existence of a decomposition of the complete graph Kn(the complete graph from which a 1-factor has been removed, Kn - F) into cycles of different lengths has been investigated several times.

In this talk first we will decompose the complete bipartite graph Km,n (K2n+1,2n+1 - F, where F is a 1-factor of K2n+1,2n+1) into cycles of lengths 4, 6, or 8. Second, we will show the decompositions of 2-fold complete bipartite graph 2Km,n into cycles of lengths 4, 6, or 8 for each positive integers m, n and m <= 2, n <= 2. Then, we will decompose the 2-fold complete tripartite graph Kp,q,r into most cycles, that is, pq + /lceil (p + q)r/2 /rceil cycles, for each triple p, q, r of positive integers and p <= q <= r.



Chuck Biehl & Sheel Ganatra The Charter School of Wilmington, Wilmington , Delaware

Traffic Flow Theory and Transportation Networks

The workings of traffic flow theory and flow networks have long been used to analyze and optimize traffic patterns, especially in urban areas. While traffic flow theory associates with the properties of a vehicle or vehicles on a road given different localized conditions, transportation networks deal with the interrelations of many roads as a whole, taking the length and optimum flow on a road to find optimizations on many roads.

Transportation networks are represented by weighted graphs or digraphs in which edges are roads and vertices are intersections. To make this model realistic in problems such as optimization, metrices are assigned to each edge, along with a flow, which is often determined by the metric space. Several properties associated with metric spaces are non-negative distances, symmetry, and the triangle inequality. In transportation networks, the symmetric property can be ignored due to one way streets, which are represented by directed edges.

Traffic flow theory uses equations to model the properties of cars with respect to position and time. The fundamental relation in traffic flow theory is: Flow = Density x Speed. In other flow theories, such ones that deal with water flow through pipes, density and speed are independent variables. However, in traffic flow theory, density and speed are dependent on each other, and on flow. Traffic flow theory^s applications extend to describing the motion of one car on a highway to determining the effect several cars have on each other.



Michael L. Gargano Pace University

Complement domination
Talk based on joint work with L. V. Quintas, J. Rubens and M. Courtney

Let D be a weakly connected digraph, and assume D contains no loop nor multiple arc. If u and v are vertices of D, then u dominates v if and only if (u,v) is an arc of D. In this paper, an algorithm for solving the following problem is given. Given D and a positive integer k, is it possible to partition the vertex set of D into two non-empty sets X and Xc (the complement of X) such that

(a) each vertex in X dominates every vertex in Xc (such a partition is called a complement domination partition)

and

(b) X is maximal such that |X| < k?

Some experiments and open problems will also be presented.



Heather Gavlas Grand Valley State University

Cycle Decompositions of Kn and Kn-I

It is natural to ask when a complete graph on n vertices admits a decomposition into cycles of a fixed length. The necessary conditions are that n is odd and that the number of edges in the complete graph is a multiple of the cycle length. This question can be extended to complete graphs with an even number of vertices by removing a 1-factor. We will discuss the solution when the number of vertices in the complete graph and the cycle length are of the same parity.



Terry Griggs The Open University

Anti-Pasch Steiner Triple Systems

A Pasch configuration in a Steiner triple system is a collection of four triples whose union has cardinality six. Such a configuration must be isomorphic to {a, b, c}, {a, y, z}, {x, b, z} and {x, y, c}.

An anti-Pasch Steiner triple system is one which contains no Pasch configurations.

It is well known that Steiner triple systems, STS(v), exist if and only if v = 1 or 3 (mod 6). and it has been a long standing conjecture that anti-Pasch Steiner triple systems also exist for all these values except for v = 7 or 13.

The case in which v = 3 (mod 6) was first solved by Brouwer in 1979.

The case in which v = 1 (mod 6) appears to be more problematical but has also recently been solved.

The details are in two papers, the first by Alan Ling, Charlie Colbourn, Mike Grannell and myself and the second by Mike Grannell, Carol Whitehead and myself which will appear this year.

In this talk I will describe the stages in the eventual solution of the anti-Pasch problem and put it in context of what further problems still need to be considered.



Alan Hartman IBM Research Laboratory, Haifa, Israel

The Mathematics of Software Engineering

Software affects almost every aspect of our lives in the 21st century. It manages our telephone networks, nuclear power plants, air-traffic control systems, and our banking and financial institutions - to name just a few. Unfortunately many software systems are "fragile" in the sense that they are unreliable, suffer from security and performance lapses, and are difficult to maintain and upgrade to satisfy new demands. Software Engineering, as it is practised today, is an art rather than a science. This talk will discuss research in Software Engineering, the creation and analysis of mathematical models of software systems, and how these ideas promise to provide tools for combatting the fragility of software.



Irith Ben-Arroyo Hartman Open University and Haifa University

Path Partitions and Colorings in Directed Graphs

In this talk we present some results and open problems related to path partitions, path coverings, and colorings in directed graphs.

A path partition in a directed graph G is a set of vertex-disjoint paths that cover the vertex set of G. Dilworth's Theorem states that if G is a di-graph of a poset, then the minimum number of paths in a path partition equals the size of a maximum independent set in G. Greene and Kleitman extended Dilworth's Theorem by considering, for each positive integer k, a collection of k disjoint independent sets in a poset. Berge made a conjecture in 1982 extending the Greene-Kleitman Theorem to all di-graphs. The conjecture is still open. We present some other conjectures and results extending the Greene-Kleitman Theorem to all di-graphs.



Dean Hoffman Auburn University

Perfect graphs and good charactarizations

We give an introduction to vertex coloring, perfect graphs, and good characterizations, with examples to illustrate the intimate interconnections among these.



Alexander Kelmans Rutgers University and University of Puerto Rico

On packing subgraphs in a graph

Let G be a graph and F a connected subgraphs of G. A subgraph H of G is called an F-packing if each component of H is isomorphic to F. The F-packing problem is that of finding an F-packing having the maximum number of vertices (or, the same, the maximum number of components).

A spanning F-packing of G is called an F-factorization of G. It provides a partitioning of V(G) into subsets each of which induces in G a subgraph isomorphic to F.

If F is of two vertices then the F-packing problem is a classical matching problem that can be solved in polynomial time. If F has at least three vertices (for example, F is a 3-vertex path) then the F-packing problem is known to be NP-hard.

We consider the F-packing problem when F is either a 3-vertex path or, more generally, a tree.

We will discuss for some classes of graphs

(1) asymptotic results (due to A. Kelmans, D. Mubayi, B. Sudakov),

(2) approximation and worst case results (due to A. Kelmans, D. Mubayi), and

(3) exact results (due to A. Kaneko, A. Kelmans, T. Nishimura).



Curt Lindner Auburn University

A small embedding for partial 4-cycle systems

A partial 4-cycle system of order n can be embedded in a 4-cycle system of order approximately 2n + (square root)2n. This isn't the best possible result.....but it's pretty good. The best result is probably around n + (square root)n. This is a very elementary talk and is designed to generate interest in reducing the known bound.



Geoffrey L. McKenna George Washington University

Self-Complementary Graphs and Their Lexicographic Products

A graph G is said to be self-complementary if it is isomorphic to its complement. Given a pair of graphs G and H, their "lexicographic product" G[H], is ontained by replacing each vertex of G by a copy of H, and each edge of G by the edge set of the complete bipartite graph adjoining the two indicated copies of H. For arbitrary graphs, the automorphism group A(G[H]) contains the wreath product of A(G) and A(H), in some cases properly.

Given two self-complementary graphs G and H, it is true that their lexicographic product G[H] is self-complementary. It is also true that when G and H are self-complementary, in the construction of the lexicographic described above, each copy of H is a block of imprimitivity of the automorphism group A(G[H]). In consequence, A(G[H]) is precisely the wreath product of A(G) and A(H). Both of these claims are believed to be new.

Two other new claims are given: First, for each positive integer n, their exists a unique graph Un which satisfies the folowing three constraints:

i. Its order is 4n.

ii. It is self-complementary.

iii. It has a unique matching.

The second new claim is that the degree sequence of a self-complementary graph of order 4n is distinguished by the following trait: Given any j between 1 and 2n, the sum of the degrees of the 2j vertices of least degree is at least 2j2. This bound is best possible, and is realized for each j in [2n] by Un.



Louis V. Quintas Pace University

Some partition problems involving Hamiltonian Paths
Talk based on joint work with K.T. Balinska

Let G be a connected graph. An edge e of G is called a Hamiltonian Path Edge, if there exists a Hamiltonian path in G that contains e. Since every edge in G is either a Hamiltonian path edge or not, the edges E(G) of G are uniquely partitioned into two sets Y(G) and N(G), where Y(G) is the set of Hamiltonian path edges of G. Clearly, if G does not contain a Hamiltonian path, then E(G) = N(G) and if every edge is in some Hamiltonian path of G, then E(G) = Y(G).

Problem 1. Characterize graphs G such that E(G) = Y(G).

Problem 2. Determine the (Y, N) partition of E(G) for well known and/or interesting graphs G.

By an f-graph we mean a graph having no vertex of degree greater than f. Let U(n, f) denote the graph with vertices the set of unlabeled f-graphs of order n. A pair of f-graphs {G, H} is an edge in U(n, f) if and only if H can be obtained from G by the addition of a single edge.

Variations of graphs of this type play a role in a variety of contexts. For example, G can be the transition digraph for a random process, the vertices of G can be interpreted as molecular graphs, or G can be studied strictly with respect to its graph theoretical properties. It is of particular interest that the study of such graphs ranges from topics suitable for an introduction to graph theory with quite elementary problems to problems that are considered very difficult. As an illustration, consider the following.

Problem 3. For what values of n and f does U(n, f) contain a Hamiltonian path?

Problem 4. For what values of n and f does U(n, f) have a perfect matching?

We shall report on the status of our work in progress concerning Problems 1 to 4.



Michael Edwin Raines Western Michigan University

Embedding Extended Mendelsohn Triple Systems
Vince Castellana and Michael Raines

n extended Mendelsohn triple is an ordered triple of the form (x,x,x), (x,x,y), or (x,y,z), called a loop, a directed lollipop, and a directed 3-cycle, respectively. An extended Mendelsohn triple system (V,B) of order n and index \lambda, or EMTS(n, \lambda), is a collection B of extended Mendelsohn triples defined on an n-set V such that every ordered pair of (not necessarily distinct) elements of V is contained in exactly \lambda extended triples of B. An extended Mendelsohn triple system (V, B) of order n and index \lambda is said to be embedded in an extended Mendelsohn triple system (V', B') of order v and index \lambda if V \subseteq V' and B \subseteq B'. In this talk, we give necessary and sufficient conditions for embedding an EMTS(n,\lambda) in an EMTS(v, \lambda).



K. Brooks Reid California State University, San Marcos

Partitions of tournaments into transitive subtournaments

In this talk we consider partitions of the vertex sets of tournaments so that the blocks induce transitive subtournaments. Such partitions are easy to find if there is no restriction on the orders of the transitive subtournaments and if there is no restriction on the number of transitive subtournaments. Indeed, merely remove the largest transitive subtournament, then iterate this in the remaining subtournament. We treat two problems concerning partitions of tournaments into transitive subtournaments. In the first problem all transitive subtournaments are to be the same order (and, hence the number of such transitive subtournaments is fixed). In the second problem the number of transitive subtournaments is fixed (but their orders may vary).



Fred S. Roberts DIMACS/Rutgers University

From Garbage to Rainbows: The Many Applications of Graph Coloring

The simple concept of coloring a graph has a long history and has been a fundamental idea in graph theory. This talk will survey its many applications, such as channel assignments in telecommunications, task scheduling, traffic phasing, fleet assignment, and mobile radio frequency assignment. We will also describe generalizations of the standard notion of graph coloring that arise from applications.



Christopher Rodger Auburn University

Amalgamations of graphs

In this talk, amalgamations of graphs will be described, some of the history of their uses will be presented, and latest applications of the technique will be discussed.



Alexander Rosa McMaster University

Specialized Colouring and Maximal Arcs

We consider colourings of Steiner triple systems and Steiner systems S(2,4,v) in which blocks have prescribed colour patterns, as a refinement of classical weak colourings. We study the question of the existence of a colouring of given type in which exactly k colours are used, as well as the question of uncolourable systems. We also examine the related question of the existence of S(2,4,v) with maximal arcs.



Moshe Rosenfeld Pacific Luthera University

"Geometric" Graph Partitions

Certain partitions of graphs occur as a byproduct of other investigations. For instance, the edge set of K12 can be partitioned into 2 disjoint copies of an icosahedron plus a 1-factor. The edge set of the complete graph K2n can be partitioned into two copies of "some" G(2n,n-1) graphs (G(2n,n-1) an (n-1)-regular graph of order 2n) plus a 1-factor. Who are these graphs? Can these partitions be "extended uniformly" so that all edges will be treated equal? For instance, 5K12 can be partitioned into 11 copies of an icosahedron so that each edge appears in 5 icosahedra. These partitions are a "natural" byproduct of some geometric structures. These topics and some related open problem will be discussed.



Benjamin Sudakov Princeton University

Asymptotically optimal tree-packings in regular graphs
Joint work with A. Kelmans and D. Mubayi

Given a graph G and a family F of graphs, an F- packing of G is a subgraph of G each of whose components is a member of F. The F-packing problem is to find an F--packing of the maximum number of vertices. The very special case of F-packing when F=K2, a single edge, is simply that of finding the size of a maximum matching. This problem is well-studied, and can be solved in polynomial time. On the other hand, the F-packing problem even when F is a path of length at least two, is known to be NP-complete.

Here we consider an asymptotic version of this problem, where F consists of a single member that is a tree with t vertices. Our main result is the following.

Let T be a tree on t vertices and let e > 0. Suppose that G is a d-regular n vertex graph satisfying d >= (128t3/e2)ln( 128t3/e2). Then G contains (1-e)n/t vertex disjoint copies of T.



Evan Bruce Wantland Western Montana College of the University of Montana

Amalgamations of graphs as a tool for k-factor embeddings
A. J. W. Hilton, C. A. Rodger, E. B. Wantland*

Given graphs G and H with |V(G)| >= |V(H)| and |E(G)| = |E(H)|, we say H is an amalgamation of G (or G is a detachment of H) if there exist a bijection f: E(G) -> E(H) and a surjection p: V(G) -> V(H) such that:

i) if e is an edge in G joining x and y, then f(e) is an edge in H joining p(x) and p(y) (if p(x) = p(y) then f(e) is a loop), and

ii) if e is a loop on x in G, then f(e) is a loop on p(x) in H.

In this presentation we will discuss necessary and sufficient conditions for the embedding of an edge-colored graph H into an edge-colored graph G in which the edges of each color induce a k-factor. We will give results when H and G are complete graphs or complete multipartite graphs and for different edge-connectivity conditions on the k-factors. We will obtain these results by investigating necessary conditions on amalgamations of k-factorizations and then showing when these are sufficiaent by reconstructing a k-factorization from an amalgamation.





Updated July 14, 2000