CMS Winter 2003 Meeting

Graphs and Matroids / Graphes et matroîdes
Org: Luis Goddyn (Simon Fraser) and/et Ladislav Stacho (Simon Fraser)

KATHIE CAMERON, Wilfrid Laurier University, Waterloo, Ontario  N2L 3C5
Finding induced matchings and dissociation sets in graphs

A matching M in a graph G is a subset of the edges of G such that each vertex of G is met by at most one edge of M. An induced matching in a graph G is a matching M such that no pair of edges of M is joined by an edge of G; that is, an induced matching is a matching which forms an induced subgraph of G. We can think of an induced matching as a set of edges which induces a subgraph where all vertex degrees are 1.
A dissociation set is a set of vertices which induces a subgraph where all degrees are 0 or 1.
We consider the problems of finding a largest induced matching and a largest dissociation set.
As is typical in the field of graph algorithms, we show these problems to be hard in certain classes and easy in others.

DALIBOR FRONCEK, University of Minnesota Duluth, USA
Factorizations of complete graphs into spanning trees

Although the factorization of complete graphs into isomorphic spanning trees is a very natural problem, it has not received much attention. One reason may be that the labeling methods that are often used for isomorphic decompositions of complete graphs K_2n+1 into 2n+1 copies of trees with n+1 vertices (like graceful labeling) do not work for factorizations unless they are modified. Such a modification is not hard to discover, as we show in this talk when we define a blanded labeling and its generalizations. However, it is much harder to prove the existence of a blended labeling even for very simple classes of trees. For instance, it is well known that all caterpillars are graceful. On the other hand, it is still not completely known which caterpillars of diameter 5 admit a blended labeling.
We proved recently that a complete graph K_4k+2 can be factorized into isomorphic trees with any diameter d where 3 £ d £ 4k+1. We will show that for each K_4k, where k ¹ 2^q, there also exists an isomorpic factorization into trees with any diameter d where 3 £ d £ 4k-1. Partial results for k=2^q will be also mentioned. If time permits, we will present the complete characterization of caterpillars of diameter 4 that factorize complete graphs K_4k+2 and some related results.

PENNY HAXELL, University of Waterloo, Waterloo, Ontario
Independent transversals in r-partite graphs

An independent transversal in an r-partite graph G is an independent set in G consisting of exactly one vertex from each partite class. For arbitrary positive integers n and r we determine the largest integer D = D(r,n), for which any r-partite graph with partite sets of size n and of maximum degree less than D has an independent transversal. This value was known for all even r. Here we determine the value for odd r and find that D(r,n)=D(r-1,n). Informally this means that the addition of an odd-th partite set does not make it any harder to guarantee an independent transversal.
This talk represents joint work with Tibor Szabó.

PETER HORAK, University of Wasington, Tacoma, Washington, USA
Covering vertices of a graph by trees

Several ways have been introduced to measure how far a graph G is from having a hamiltonian cycle/path. In this talk we deal with two of them that involve trees.
On one hand, one can understand a hamiltonian path as a spanning tree with the maximum degree two. Then it is natural to ask what is the smallest number k so that there is in G a spanning tree of the maximum degree k. Win showed that k £ é[(|G|-1)/(d)]ù, where d stands for the minimum degree of G. There are many variations, extensions and generalizations of the result.
On the other hand, it is possible to see a hamiltonian path as a spanning forest. Then, to measure how far is G from a hamiltonian graph, one asks what is the minimum number m of paths covering all vertices of G. In a classical paper og Gallai and Milgram it is shown that m is at most the independence number of G. Also in this case there are many papers dealing with the topic, mostly with the complexity aspects of the problem.
To get a deeper insight into the problem we discuss the following common generalization of the above two approaches. Let G be a graph and k be a natural number. Determine the smallest number m so that there are disjoint trees T₁,...,T_m, each of them of maximum degree at most k, covering the vertices of G.

JING HUANG, Department of Mathematics and Statistics, University of Victoria, Victoria, British Columbia  V8W 3P4
Bigraphs of Ferrers dimension two and circular arc graphs

In this talk, I will describe relations among interval digraphs, interval containment digraphs, interval bigraphs, bigraphs of Ferrers dimension two, and circular arc graphs of clique covering number two.

GARY MCGILLIVRAY, University of Victoria, Victoria, British Columbia
Near-Unanimity functions of reflexive graphs

We report on joint work with Richard C. Brewster, Tomas Feder, Pavol Hell and Jing Huang.
Let H be a graph and k ³ 3. A near-unanimity function of arity k is a homomorphism g from the k-fold Cartesian product H^k to H such that g(x₁, x₂, ..., x_k) = a whenever at least k-1 of the x_i's equal a. These can be viewed as an algorithmic tool in the following sense: Feder and Vardi [SIAM J. Computing, 1998] proved that if a graph H admits a near-unanimity function, then the homomorphism extension problem for (equivalently, retraction to) H is polynomialy solvable. It is therefore of interest to determine which graphs admit a near-unanimity function.
We focus on reflexive graphs. It is proved that every reflexive chordal graph admits a near-unanimity function, and several bounds for the arity of these functions are given. In particular, every reflexive chordal graph with n vertices has a near-unanimity function of arity at most n -Ön + 1. We also exhibit nonchordal graphs which admit near-unanimity functions. Forbidden substructures for reflexive graphs that admit a near-unanimity function are then investigated. It follows from our results that, for instance, that no reflexive cycle of length at least four admits a near-unanimity function of any arity.

SEAN MCGUINNESS, Adelphi University, Garden City, New York, USA
Sequential transversals in matroids

Let S be a finite set and S be a collection of subsets of S. For each x Î S let S_x = {T Î S | x Î T }. Suppose we choose elements x₁, ...,x_n in such a way that we first choose x₁ belonging to some subset of S_x₁. For i=2, ...,n we choose x_i Î S_{x_i} \S_x₁ È¼ÈS_{x_i-1}. We call the set { x₁, ... ,x_n } a sequential transversal of S, and we let T_S be the set of all sequential transversals of S, which includes Æ as well. We examine conditions under which the pair (T_S,S) is matroid. It is shown that every matroid on a set S can be defined as pair (T_S,S) where T_S is order-independent; that is, the elements in any sequential transversal can be picked in any order. For S Í 2^S, various conditions and examples are provided in which (T_S, S) is a matroid. We also provide a counterexample to a conjecture of Jones.

JENNY MCNULTY, The University of Montana
Non-orientable matroids and characteristic sets

The characteristic set c(M) of a matroid, M, is the set of primes p and possibly 0, so that k Î c(M) if and only if M is representable over a field of characteristic k. Much work was done to classify characteristic sets and to construct rank 3 matroids, M, with c(M)=c for each possible characteristic set c. We investigate several classes of rank 3 sequentially unique matroids, M, with c(M)=p, such as the Reid matroids. We show these classes are not orientable. Lastly, we discuss several open problems relating orientability and characteristic sets.

WENDY MYRVOLD, Department of Computer Science, University of Victoria
Hunting for torus obstructions

A torus is a surface shaped like a doughnut. A graph is toroidal if it embeds on the torus with no crossing edges. A topological obstruction for the torus is a graph G with minimum degree three that is not embeddable on the torus but for all edges e, G-e embeds on the torus. A minor order obstruction has the additional property that for all edges e, G contract e embeds on the torus.
The aim of our research is to find all the obstructions to the torus (both minor order and topological). To date, we have found 239,322 topological obstructions and 16,629 minor order obstructions. Previously, only a few thousand had been determined. This talk discusses the techniques used to find these obstructions and suggests avenues for completing this research.

NANCY NEUDAUER, Pacific University, Forest Grove, Oregon
Graph representations of a bicircular matroid

Let G be a graph (loops and parallel edges allowed) with vertex set V={1,2,¼,n} and edge set E. In the classical matroid associated with a graph, a set of edges is independent in the matroid if it contains no cycles, and the circuits of the matroid are the single cycles of G. The bicircular matroid of G is the matroid B(G) defined on E whose circuits are the subgraphs which are subdivisions of one of the graphs: (i)  two loops on the same vertex, (ii)  two loops joined by an edge, (iii)  three edges joining the same pair of vertices.
The bicircular matroid is known to be a transversal matroid and thus can be represented by a family of sets, called a presentation. Given a transversal matroid, we can determine whether it is bicircular. I will show that, given any presentation of a bicircular matroid, we can find a graph representing the matroid, and that, in some cases, there is more than one graph. We investigate how the graphs representing a bicircular matroid are related, and what this means in terms of their presentations as transversal matroids.

ORTRUD OELLERMANN, University of Winnipeg, Winnipeg, Manitoba
Contour vertices and convexity notions in graphs

The interval between a pair u,v of vertices in a graph G is the collection of all vertices that belong to some shortest u-v path in G. A set S of vertices is convex if it contains the interval between all pairs of vertices in S. The convex hull of a set S of vertices in a graph G is the smallest convex set that contains S. A vertex v of a graph G is a contour vertex of a set S if its eccentricity, ecc(v)=max{d(v,u) | u Î V(G)}, is at least as large as that of its neighbors in S. We show, for any connected graph G and any convex set S of G, that S is the convex hull of the contour vertices of S. The closure of a set S of vertices of a graph is the union of intervals between pairs of vertices of S taken over all pairs of vertices of S. A set S of vertices of G is a geodetic set if its closure is V(G). The smallest cardinality of a geodetic set for a graph G is called the geodetic number of G. We show that in general the problem of finding the geodetic number of a graph is NP-hard. For distance hereditary graphs it is shown that the contour vertices form a geodetic set. The Steiner interval of a set S of vertices in a graph is the union of all vertices that belong to some Steiner tree for S (i.e., a tree of smallest size that contains S). A set S of vertices in a graph G is a Steiner geodetic set if its Steiner interval is V(G). The smallest cardinality of such a set is the Steiner geodetic number of the graph. We compare the geodetic and the Steiner geodetic number of a graph and show how contour vertices can be used to find the Steiner geodetic number for most distance hereditary graphs.

BRUCE REED, School of Computer Science, McGill University
An odd version of Hadwiger's conjecture

A clique minor of order l is a set of l vertex disjoint trees between every pair of which there is an edge. It is odd if we can two colour it so that each tree is properly coloured but every edge between the trees is monochromatic. About 10 years ago Gerards and Seymour conjectured that if a graph contains no odd clique minor of order l then it is l-1 colourable. We prove an approximate version of this result and discuss some related results. This is joint work with an author list which has not yet been fully determined but includes Gerards and Seymour.

NICK WORMALD, University of Waterloo, Waterloo, Ontario  N2L 3G1
Tournaments with many Hamilton cycles

The object of interest is the maximum number, h(n), of Hamilton cycles in an n-tournament. By considering the expected number of Hamilton cycles in various classes of random tournaments, we obtain new asymptotic lower bounds on h(n). The best result so far is approximately 2.85584¼ times the expected number g(n) of Hamilton cycles in a random n-tournament, and it is conjectured that h(n) ~ cg(n) where c » 2.855958. The same statements hold for Hamilton paths.

ROGER YU, Cariboo

BING ZHOU, Trent University, Peterborough, Ontario  K9J 7B8
List colouring the hypergraph of maximal cliques of planar graphs

We consider some problems related to colouring and list-colouring the hypergraph of maximal cliques of planar graphs. In particular, we show that if each edge in a planar graph G lies on at least one 3-cycle, then the hypergraph of maximal cliques of G is 2-choosable.