DIMACS DREI '99
Week 1 Topic: Matchings in Graphs and their Applications
July 19 - 23, 1999

Abstracts

Brian Alspach, Simon Fraser University

1-factorizations of Cayley graphs

It has been conjectured that every connected Cayley graph on an even order group has a 1-factorization. I shall present a survey of the current status of this conjecture.

Some cycle decomposition problems

Rently the problem of decomposing complete graphs and complete graphs minus a 1-factor into cycles of fixed length has been completely solved. I will present a survey on some of my other favorite cycle decomposition problems.

Richard Anstee, University of British Columbia

Orthogonal matchings
Joint work with L.Caccetta

Let G be a graph which has been decomposed as the union of m spanning subgraphs F_1,F_2,...,F_m. An orthogonal matching is a matching M with |E(F_i)\cap M| for i=1,2,..., m. We consider cases where each F_i is regular of degree k (and so G is regular of degree km) and we seek a matching M with |E(F_i) \cap M| <= 1. For k=1, we are able to show the existence of a matching M of size at least m - {2/3}m^{2/3} (for a large m). A special case of this is looking for a transversal in a latin Square for which Schor has obtained the best bound For k=2, Alspach has conjectured that we should be able to find an orthogonal matching M of size m. We show the existence of a matching M of size at least m-m^{2/3} (for large m). The arguments use special augmenting paths.

Peter Christopher, Worcester Polytechnic Institute

Monotonicity of cages

A (k,g)-graph is a k-regular graph with girth g. A (k,g)-cage is a (k,g)-graph of smallest order f(k,g). Cages have been shown to be monotonic in the sense that f(k,g1) < f(k,g2) whenever g1 < g2. We examine a related question: Is f(k1,g) < f(k2,g) whenever k1 < k2 ?

Margaret B. Cozzens, University of Colorado

The Process of Mathematics

In science education today we talk of the process of science and ways of encouraging students to "do science", not just learn about it, through hands-on, inquiry-based lessons and units. Not much has been said about the process of mathematics, nor what would be meant by inquiry in mathematics, yet there is a great deal said about problem solving and modeling using mathematics in the NCTM Standards. How the problems are constructed, where they come from, how one attempts to search and iterate for solutions, and how one discovers new mathematical results to use in the solution is a mystery to most students and teachers. This is a talk that will have something in it for everyone in the audience, teachers, students, and senior researchers. I will try to illustrate the process of mathematics by looking at a problem that exists in software design, construct formulations of the problem, indicate the search for solutions of the formulations, indicate known results, and how one would develop new mathematical tools to solve the problem. The ultimate or optimal answers are not yet known, so the audience will be able to search for solutions as well. The only hint for now is that the problem formulation involves network stability.

Edward Dobson, Mississippi State University

On packing trees with a vertex of large degree into the complete graph

In 1976 Gyarfas and Lehel conjectured that every sequence of trees T_1,T_2,...,T_n such that |V(T_i)| = i for all 1<=i<=n, can be packed into K_n. This conjecture is usually referred to as the Tree Packing Conjecture. We will discuss recent results on this conjecture concerning sequences of trees which have a vertex of "large" degree. Similar type results for Ringel's conjecture, which states that 2n + 1 copies of a tree of order n+1 can be packed into K_{2n + 1} will also be discussed, as well as recent progress on related questions.

Hongbing Fan, Simon Fraser University

Some applications of matching theory

In this presentation I will introduce three real problems which were modeled as graph problems and solved by matching theory. The first is a Chinese postman problem: to find a minimum distrance route for a postman who starts from a post office and goes along each street at least once and ends at the post office. This problem was raised in 1962 by Meigu Guan and solved by Edmonds. It was one of the most beautiful applications of classical matching theory. The second is a special garbage collection problem: to find a route with minimum number of U-turns for a large garbage collecting truck which goes along each street from each direction exactly once. This problem was again formulated to a graph problem and solved by using the matroid matching theory. The third one is a routing problem in VLSI circuit design. The focus of this presentation is on modeling real world problems by graph and trying to solve them by using matching theory. Some background stories will be covered.

Michael Gargano, Pace University

#### Minimal cost dynamic matchings using a genetic algorithm

Given a complete graph on an even number of vertices and a time dependent cost function on each edge what is a minimal total cost perfect matching if only one edge is allowed to be chosen at each time period? A genetic algorithmic approached will be discussed.

Alan Hartman, IBM Haifa Research Laboratory

#### Graph theoretical problems in formal verification

The integrated circuits built by the micro-electronics industry in 1999 are several orders of magnitude more complex than those of a decade ago. A design error discovered late in the development cycle can result in the loss of hundreds of millions of dollars. The current technologies for verification of designs include massive simulations and, more recently, formal verification techniques. Formal verification begins with the construction of a finite state automaton which represents the design of the circuit. Properties of the design are then formulated in a temporal logic language. These properties can be associated with sets of paths in the labeled digraph of the finite state automaton. Formal verification consists of proofs of the existence (or non-existence) of these paths in the finite state automaton. One of the major issues in this area is how to represent the enormous digraphs involved in these computations. The current technology of choice for this representation problem is Binary Decision Diagrams (BDDs) which are themselves objects of considerable graph theoretical interest. This talk will survey some of the issues and hopefully encourage the interest of the graph theory community in this exciting area of research.

Irith Hartman, Open University and Western Galil College

#### Ranking intervals under visibility constraints

Let S be a set of n closed intervals on the real line. A ranking assigns to each interval s, a distinct rank, p(s) in {-1,2...,n} We say that an endpoint x of an interval s is exposed if no interval t with p(t) < p(s) contains x. A ranking is optimal if the number of exposed endpoints is maximum. We characterize all optimal rankings of a given set S, and present a polynomial time algorithm which finds an optimal ranking. The results have applications to intersection problems for intervals as well as to channel routing problems which arise in layouts of VLSI circuits. This problem was first posed by H. Edelsbrunner in 1982 and was solved simultaneously in 1989 by two teams of researchers: Edelsbrunner, Overmars, Welzl, and Hartman with Feldman.

Penny Haxell, University of Waterloo

Matching in bipartite graphs and hypergraphs

Hall's Theorem gives a necessary and sufficient condition for a bipartite graph to have a complete matching. We define a more general object called a "bipartite hypergraph", in which there is a natural notion of "complete matching", and give a theorem analogous to Hall's Theorem for these more general objects.

Dean Hoffman, Auburn University

Universal vertices and the ole switcheronny

This will be an elementary talk on two fundamental concepts in matching theory: the role of universal vertices, those contained in every maximum matching, and path interchanges (= the ole' switcheroony). The emphasis will be on a game children could play on a graph, 'Slither'. The ideas introduced here are actually strong enough to prove both Hall's classic theorem on matchings in bipartite graphs, as well as Tutte's celebrated theorem on perfect matchings.

#### Matching designs

If M and G are simple graphs, an M-design on G is a set of subgraphs of G (called the blocks of the design), each isomorphic to M, with the property that every edge of G is in exactly one block. The decision problem M-DESIGN, for fixed M, is the following: INPUT A simple graph G QUESTION Is there an M-design on G? It is known that M-DESIGN is NP-Complete if at least one component of M has at least three edges. We have some good news at the other end of the spectrum; we give a poly-time algorithm when M is a matching of k independent edges.
Ed Ihrig, Arizona State University

#### The Role of symmetry in the construction, recognition and classification of 1-Factorizations of the complete graph

There are three basic problems associated with graphical structures in general, and 1-factorizations of a graph in particular. The first is to find ways to construct the structure, the second is to find techniques for determining when two structures are essentially different (not isomorphic), and the third is to find natural ways to classify these structures. In this talk we will discuss a number of ways in which study of the automorphism groups of 1-factorizations of the complete graph has cast light on each of these questions. We will give examples of how understanding of the structure of these automorphism groups has given rise to new ways to construct 1-factorizations. In particular, a modified version of the even starter construction will be discussed. Also, it will be shown how understanding of the automorphism group of a 1-factorization can be used to discover whether newly constructed 1-factorizations are isomorphic to already known 1-factorizations, even in the case when the automorphism groups of the two 1-factorizations are isomorphic. Some results will be given concerning starter induced 1-factorizations (whose automorphism groups frequently are isomorphic to just the original starter group). Finally, it will be shown how certain interesting properties of 1-factorizations can be detected in the structure of their automorphism groups. This will suggest that certain features of automorphism groups may be useful in distinguishing between general types of 1-factorizations.

#### Open questions concerning the 1-Factorizations GK(G) of the complete graph.

GK(G), where G is a cyclic group, was discovered over one hundred years ago, and was probably the first known infinite family of 1-factorizations of the complete graph. GK(G), where G is a group of odd order, can be simply described as a starter induced I -factorization of the complete graph generated by the patterned starter; namely, the starter in which each non-identity group element is paired with its inverse. It is interesting to note that the automorphism group of GK(G) was only worked out relatively recently. This automorphism group involves an interesting new group associated with G which consists of all the near automorphisms of G. A near automorphism is a bisection f from G to itself which satisfies the property that f(xyx) = f(x)f(y)f(x) for all x and y in G. When G is abelian (and odd order) every near automorphism is an automorphism; however, when G is not abelian, the function which takes a group element to its inverse gives an example of a near automorphism which is not an automorphism. In this talk,we will describe the automorphism group of GK(G) in terms of the near automorphisms of G. We will then discuss a number of interesting open questions of both a group theoretical nature and concerning the I -factorizations GK(G). We will discuss in detail how the results outlined in the presentation effect one of the most basic unresolved questions concerning GK(G); namely, are there two non-isomorphic groups G and G' for which GK(G) is isomorphic to GK(G')?
Tao Jiang, University of Illinois

#### New upper bounds for a canonical ramsey problem

Let f(l,k) be the minimum n with the property that every coloring c: \binom{[n+1]}{2}-->{1,2,....} yields either x_0<... infty. This supports the conjecture of Lefmann, "odl, and Thomas that f(l,k)=l^{k-1}.
Alexander Kelmans, University of Puerto Rico

#### A strengthenning of the Kuratowski Planarity Criterion for graphs

Let G be a graph, and {\cal F} be a family of subgraphs of G. An edge subset A of G is called an {\cal F}--{\em packing of G} if every component of the subgraph G[A] induced by A in G is a graph in the family {\cal F}. The {\cal F--{\em packing problem} consists of finding an {\cal F}--packing A of G that covers the maximum number of vertices. The {\cal F}--packing problems have extensively been studied by many authors for different classes of families {\cal F}. Clearly the complexity status of an {\cal F}--packing problem essentially depend on the family {\cal F}. It is not surprising that the problem turns out to be NP-hard for most of the families {\cal F}. Surprisingly the problem can be solved in polynomial time for some non-trivial classes of families. For example, the S_n-packing problem (where S_n is the set of stars of G having at most n edges) is a simplest generalization of the matching problem that turns out to be polynomial. A more complicated IS_n-packing problem (where IS_n is the set of all induced stars of G having at most n edges) is also polynomial. Moreover we have shown that many classical results on matchings (such as the Tutte 1-Factor Theorem, the Berge Duality Theorem, the Gallai-Edmonds Structure Theorem, the Matching Matroid Theorem) can be extended to induced n-star packings in a graph. In this talk we will discuss some natural generalizations of the S_n and IS_n-packing problems. We will also discuss (joint work with Y. Egawa and M. Kaneko) relations between the duality theorem for IS_n--packing problem and some variations of the Hall theorem. It is known that the Lambda--packing problem (the problem of packing 2--edge paths in a graph) is NP--hard. We present some results (joint work with Hikoe Enomoto, A. Kaneko, and T. Nishimura) on the Lambda--packing problem for certain classes of graphs.
Ralf Keuthen, University of Nottingham

#### New side constraints for the traveling salesman problem Arising in printed circuit board assembly

The Traveling Salesman Problem (TSP) is one of the most studied problems in combinatorial optimization problems. Hundreds of publications (see e.g. [6]) have been devoted to this problem. It can be described quite easily as follows: A salesman wants to visit n cities, minimizing his total traveling distance while visiting each city exactly once and then returning home.
The problem is of significant importance, both as a prototype problem for Combinatorial Optimization and since many industrial applications can be modeled as TSPs [5]. However, it is extremely hard to tackle and well known to be NP-hard. Here we would like to consider a TSP based model used in printed circuit board assembly to determine optimized component insertion sequences for automated component placement machines. In order to model this problem as a TSP, cities and inter-city distances need to be defined. This can be achieved by defining the placement locations as cities and the distances can then be defined by the time between two successive insertions. This sequencing problem has recently become of significant importance for the electronic manufacturing industry with the development of Surface Mount Technology (SMT) in Printed Circuit Board (PCB) assembly. Since surface mount introduced the possibility to mount a large number of components on a single circuit the reduction of assembly time is now probably the most important issue to further cut down production costs and increase productivity. However, the industrial printed circuit board component placement problem is more complicated as the design of the production line and machine specifications introduce additional restrictions on the TSP. Schematically can the assembly of printed circuit boards on a typical production line be divided in three problems: 1. the assignment of component types to machines, 2. the assignment of component types to component feeder locations for each machine, 3. the component placement sequencing for each machine. Here we are considering a single component placement machine, assuming that the first problem, the allocation of component types to machines, has already been solved. Many publications have been devoted to this complex optimization problem and various models and techniques have been presented by Shellwell, Buzzcott and Magazine [ 10], Ball and Magazine [ 1 ], Brad et al. [2], Leipala and Nevalainen [7], Kho and Ng [4], Moyer and Gupta [9], Foulds and Hamacher [31 and Leon and Peters [8] to name but a few. In contrast to most publications considering the problems (2) and (3), we avoid separating them and address the assignment of components to feeders as a complication of the component placement sequencing problem, i.e. we treat (2) and (3) together as a complication of the TSP. We further present some complicating factors introduced by machine specifications which may be modeled as additional side constraints on the TSP. Our aim is to investigate and discuss these side constraints arising in printed circuit board assembly.
Joe Malkevitch, York College (CUNY)

#### Finding the "middle" of a graph and why it matters

Many situations require the optimal location of a facility or a device, perhaps a firehouse, a signal amplifier, or nurse's office. It seems natural in choosing such a location to choose one which is "centrally" located. The trouble is that there are competing notions of what makes a location "central." Since graphs are a useful model for many applications, it is worthwhile to develop a theory for locating the "middle" of a graph. This talk will examine the many interesting directions and applications that flow from such an investigation.
Louis V. Quintas, Pace University

On a graph whose vertices are graphs with bounded degree
Joint work with Krystyna Balinska

Let U(n,f) be the graph whose vertices consist of the unlabeled graphs of order n having no vertex of degree greater than f and such that the vertex corresponding to the graph G is adjacent to the vertex corresponding to the graph H if and only if H is obtainable from G by the insertion of a single edge. This graph can be extended to directed graphs with arcs weighted with probabilities yielding Markov chain models which are of interest in random graph theory and in mathematical chemistry. We shall discuss results and problems which range from those applicable to undergraduate instruction to quite difficult open problems.
K. Brooks Reid, California State University at San Marcos

#### Near-Automorphisms of complete multipartite graphs

Let f denote a permutation of the n vertices of a connected graph G, and let x and y be distinct vertices in G. Define a(x,y) to be |d(x,y) - d(f(x), f(y))|, and define d(G) to be the sum of all A~(x,y), where the sum is over all the n(n-1)/2 unordered pairs of distinct vertices x and y of G. Permutation f (of the vertices of G) is an automorphism of G if and only if s(G) = 0. Let p(G) denote the smallest positive value of s(G) among the n! permutations f of the vertices of G. A permutation f for which p(G) = s(G) is called a near -automorphism. G. Chartrand, H. Gavlas, and D. W. VanderJagt [ "Near-Automorphisms of Graphs," Graph Theory, Combinatorics, and Applications. Vol.1 (Proceedings of the 1996 Eighth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms, and Applications), Y. Alavi, D. Lick, and A.J. Schwenk (Editors), New Issues Press, 1999, pp. 181-192] conjectured that p(G) = 2n-4 when G is a path with n vertices. W. Aitken [Total Relative Displacement of Permutations, Journal of Combinatorial Theory A (1999), to appear] proved this conjecture and, among other things, characterized those permutations f for which p(G) = s(G) = 2n-4 when G is a path with n vertices. Chartrand, et. al. also claimed incorrectly that for the complete bipartite graph K(m,n), p(K(m,n)) = 2(m+n-2), for all m and n at least 2. In this talk we study near-automorphisms of all of the complete multipartite graphs and determine the corresponding values of p by transforming the problem into a combinatorial matrix problem. In particular, we correct the value of p(K(m,n)).
Chris Rodger, Auburn University

Partitioning the edges of a graph G into 4-cycles
Joint work with Hung Lin Fu

In this talk, I will discuss some of the latest results on partitioning the edges of a graph G into 4-cycles. In particular, necessary and sufficient conditions are found in the case where G is obtained from the complete graph by removing the edges of F, where F is any tree, and where F is any 2-regular graph. The case where G consists of m sets of vertices of size n, in which 2 vertices are joined by x edges if they are in the same set and y vertices if they are in different sets, is also solved.
Alexander Rosa, McMaster University

Imbalance in round robin tournaments
Joint work with Dalibor Fron

In a round robin tournament (i.e., a 1-factorization of the complete graph, each of the 2n teams plays each other's team exactly once. The n(2n-l) matches are played in 2n-l rounds each of which consists of n games played simultaneously on n distinct fields. A tournament design is a round robin tournament together with an assignment of matches to particular fields. For a tournament design, a reasonable requirement appears to be some sort of a fair and equitable distribution of teams to particular fields, as the latter may be of different quality. We introduce several measures of such an equitability, such as 'team imbalance', or 'field imbalance'. Tournament designs with minimum (team or field) imbalance are the well-known balanced tournament designs. Our objective is to determine the spectrum for imbalances in tournament designs. The latter may or may not satisfy some additional requirements.
Moishe Rosenfeld, Pacific Luthera University

#### Dancing with Eigenvalues

Dancing with Eigenvalues I.
===========================
To what extent do the eigenvalues of a Graph G determine G? One can argue that not much can be told about the graph from it's eigenvalues. After all there are many examples of graphs sharing the same spectrum. In some areas the eigenvalues play a central role. One such area is the Shannon Capacity of Graphs. The Shannon Capacity of a Graph G measures the information rate in an underlying noisy channel. In this talk an introductory survey of the Shannon Capacity and the special role of eigenvalues will be discussed. In particular, I'll try to show why determining the Shannon capacities of some "famous" graphs like the Peterson Graph, Grotsch Graph, Hoffman-Singleton Graph are of particular interest.

Dancing with Eigenvalues II.
===========================
Given 4 lines through the origin in R^3. How large can be the smallest angle among the 12 angles determined by them? In how many distinct (non-isometric) ways can one arrange 4 lines through the origin so that the angles between any pair of distinct lines are the same? These questions are part of the study of equiangular lines pioneered by J.J.Seidel. Again the central tool in studying equiangular lines are Graph Eigenvalues. In this talk I'll show how Graphs and equiangular lines are related and describe some current results and open problems.
Helen Verrall, Reed College

#### Using 1-factorizations of the complete graph to find arc-distinct Hamilton cycles in certain networks

Both de Bruijn digraphs and butterfly digraphs have been proposed and extensively studied as suitable networks for parallel computation. Furthermore, the existence of arc-disjoint directed Hamilton cycles in networks can be useful in solving communication problems. We discuss how we have used a I-factorization of K_2k to find pairwise compatible Euler tours and arc-disjoint Hamilton cycles in certain regular graphs of degree 2k, and we present our results on wrapped butterfly digraphs. We also show how we modified this idea to improve results about de Bruijn graphs of degree n and dimension 1.
Walter D. Wallis, Southern Illinois University

#### Variability of 1-factorizations

A one-factorization, or perfect matching, in a complete graph on n vertices (n even) is a way of writing the edges as (n-1) factors, where each factor consists of n/2 disjoint edges. One-factorizations exist for all even-order complete graphs, but we know only a few infinite families of them. For example, there are 396 different one-factorizations of the 10-vertex complete graph, but only a few come from known constructions; the rest were found by computer search. Our objective is to describe various properties of one-factorizations, both to increase our understanding of them and hopefully to find some more constructions of general families.
Qinglin Roger Yu, University College of The Cariboo

#### Matching extension and factor-critical in graphs

A graph G is called (k, H)-extendable if after deleting the vertices of a subgraph which is isomorphic to H the remaining graph of G has a k-factor. In this talk, we will survey the recent progress associated with this concept. Such as the properties and the characterization of (k, H)-extendable graphs; connection with k-extendable graphs and factor-critical graph. In particular, we shall discuss the minimal degree, toughness condition and degree sum conditions in these two classies of graphs.
Cun Quan Zhang, West Virginia University

#### (2 + epsilon)-flow for nearly eulerian graphs

Let r be a real number (r >= 2) A nowhere-zero r-flow of a graph G is an ordered pair (D, f) where D is an orientation of E(G) and w: E(G)-->[-r+1, -1] \cup [1, r-1] such that the total inflow equals the total outflow at every vertex of G. The concept of nowhere-zero r-flow was introduced by Goddyn, Tarsi and Zhang and is the real number line extension of the well-known integer flow problem (introduced by Tutte). The odd edge-connectivity of a graph G, denoted by lambda_o(G), is the size of a smallest odd edge cut of the graph. Odd-edge-connectivity plays a central role in the study of flow problems. Let S be any given surface and epsilon be a positive real number. We proved that there is a function phi_S(epsilon) (depends on the surface S and lim_{epsilon --> 0} phi_S(epsilon) = infty ) such that any graph G embedded in S with the odd-edge-connectivity at least phi_S(epsilon) admits a nowhere-zero (2 + epsilon)-flow. In this talk, we will also present some approach to the 5-flow conjecture and other well-known open problems.

Updated 07/15/99