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.

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.

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.

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.

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.

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.

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 K_m,n. A 2-fold complete bipartite graph 2K_m,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 K_n(the complete graph from which a 1-factor has been removed, K_n - F) into cycles of different lengths has been investigated several times.

In this talk first we will decompose the complete bipartite graph K_m,n (K_2n+1,2n+1 - F, where F is a 1-factor of K_2n+1,2n+1) into cycles of lengths 4, 6, or 8. Second, we will show the decompositions of 2-fold complete bipartite graph 2K_m,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 K_p,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.

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.

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 X^c (the complement of X) such that

(a) each vertex in X dominates every vertex in X^c (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.

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.

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.

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.

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.

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

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

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.

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 U_n 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 2j². This bound is best possible, and is realized for each j in [2n] by U_n.

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.

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

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

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.

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.

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.

Certain partitions of graphs occur as a byproduct of other investigations. For instance, the edge set of K₁₂ can be partitioned into 2 disjoint copies of an icosahedron plus a 1-factor. The edge set of the complete graph K_2n 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, 5K₁₂ 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.

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=K₂, 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 >= (128t³/e²)ln( 128t³/e²). Then G contains (1-e)n/t vertex disjoint copies of T.

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.