Pléniers et prix

Par sessions

Par conférenciers

Théorie des graphes
Org: Sebastian Cioaba (UC-San Diego), Stephen Kirkland (Regina) et Claude Tardif (RMC)

RICK BREWSTER, Thompson Rivers University
The Restricted Homomorphism Problem

The restricted homomorphism problem RHP(H,Y) asks: given an input digraph G and a homomorphism g : G ® Y, does there exist a homomorphism f : G ® H? We prove if H is hereditarily hard and Y \not® H, then RHP(H,Y) is NP-complete.

Since non-bipartite graphs are hereditarily hard, this settles in the affirmative a conjecture of Hell and Nesetril.

This is joint work with Timothy Graves.

ANDREA BURGESS, University of Ottawa
Closed trail decompositions of complete equipartite graphs

The complete equipartite graph Km *[`(Kn)] has mn vertices which are partitioned into m parts, each of size n, with two vertices adjacent if and only if they are not in the same part. The final determination of necessary and sufficient conditions for decomposition of Km and Km *[`(K2)] into cycles of fixed length was made by Alspach, Gavlas and Sajna, while necessary and sufficient conditions for decomposition of these graphs into closed trails of arbitrary lengths were proven by Balister. Since the appearance of these results, much focus has shifted towards the corresponding decomposition problems for complete equipartite graphs in general. In this talk, we consider decomposition of Km *[`(Kn)] into closed trails in the case that all trails are of the same length. In particular, we give necessary and sufficient conditions for the existence of a decomposition of Km *[`(Kn)] into closed trails of length k.

This is joint work with Mateja Sajna.

STEVE BUTLER, UC San Diego, La Jolla, CA 92093-0112, USA
Eigenvalues of 2-edge-coverings

A 2-edge-covering between G and H is an onto homomorphism from the vertices of G to the vertices of H so that each edge is covered twice and edges in H can be lifted back to edges in G. In this note we show how to compute the spectrum of G by computing the spectrum of two smaller graphs, namely a (modified) form of the covered graph H and another graph which we term the anti-cover. This is done for both the adjacency matrix and the normalized Laplacian. We also give an example of two anti-cover graphs which have the same normalized Laplacian, and state a generalization for directed graphs.

SEBASTIAN CIOABA, University of California, San Diego
Eigenvalues of Graphs

In this talk, I will present some new and old results connecting the eigenvalues of a graph and its structure.

RANDY ELZINGA, Queen's University
The Isotropic Bound on the Independence Number

If M is a symmetric matrix over some field F with 2 ¹ 0, then an M-isotropic subspace is a subspace U such that

uT Mu=0
for all u Î U. The maximum dimension of an M-isotropic subspace is called the Witt index of M. The independence number of a graph G, denoted a(G), is the maximum size of a set of pairwise nonadjacent vertices in G. If [^(A)] is an F-weight matrix for G, that is, a matrix with the property that [^(A)]ij=0 when ij is not an edge of G and [^(A)]ij Î F otherwise, then
a(G) £ iF (
This upper bound is called the isotropic bound over F. The isotropic bound is a generalization of a result due to Cvetkovi\'c which states that
a(G) £ iR (G) = n0 + min
where A is the ordinary adjacency matrix of G with Aij=1 if ij is an edge, and Aij=0 otherwise, and n0, n+, and n- denote the numbers of 0, negative, and positive eigenvalues respectively.

It is natural to ask how good the bound (1) can be, and particular for which graphs equality can be attained in the bound.

I will discuss the answers to these questions over various fields and give a classification of the graphs that attain bound over a finite field F with 2 ¹ 0.

STEVE KIRKLAND, University of Regina
Laplacian integral graphs of maximum degree 3

For a graph G on n vertices, its Laplacian matrix L can be written as L=D-A, where A is the (0,1) adjacency matrix of G, and where D is the diagonal matrix of vertex degrees. A graph is called Laplacian integral if the spectrum of its Laplacian consists entirely of integers, and the last decade has seen a growing literature on Laplacian integral graphs. In this talk, we identify all of the connected Laplacian integral graphs with maximum degree 3.

CYNTHIA LOTEN, University College of the Fraser Valley
Holes and Chordal Graphs

A hole on (reflexive) graph H is the lack of a vertex within specified distances of some the vertices of H. If a retraction exists of G, a supergraph of H, to H, then all holes on H must also be holes on G; note that this condition is necessary but not sufficient for the the existence of a retraction of G to H. The graphs H for which this necessary condition for a retraction of G to H is also sufficient are called absolute retracts with respect to holes. This generalises the well studied class of absolute retracts with respect to isomorphism.

Chordal graph have numerous useful properties due their highly structured nature. We will exploit (monophonic) convexity properties of chordal graphs to show that a hole on a chordal graph implies the existence of a hole base-a particular kind of chordal graph-as an induced subgraph, and moreover, that these hole bases can be used as building blocks of a kind of absolute retract with respect to holes.

ODILE MARCOTTE, CRM, Université de Montréal, CP 6128, succ. Centre-ville, Montréal, Québec H3C 3J7
On the relationship between graph colouring invariants and their fractional counterparts

In this talk we will survey the relationship between some graph colouring invariants (for instance the chromatic index, the chromatic number and the total chromatic number) and their fractional counterparts. In particular, we will show how results from polyhedral combinatorics enable one to prove that, in some instances, the gap between a given graph colouring invariant and its fractional counterpart is small.

DAN McQUILLAN, Norwich University
Magic Labeling of 2-regular graphs

A total labeling of a graph is a bijective map from the vertices union edges of the graph onto the consecutive integers {1,2,3,...,v+e}, where v is the number of vertices and e is the number of edges. The total labeling is said to be vertex-magic if, at each vertex, the sum of the vertex label and all incident edge labels is a constant. Graphs which have a vertex-magic total labeling are called vertex-magic graphs. Most work on vertex-magic total labelings has been done this century, although Kotzig and Rosa [1] were the first to show that every cycle is vertex-magic. They asked for a classification of vertex-magic 2-regular graphs, and the answer is still far from known.

We will describe some of the progress on this problem. MacDougall has conjectured that all regular graphs of degree at least two are vertex-magic, other than two disjoint copies of a 3-cycle (which is not vertex-magic). We prove that any other disjoint union of 3-cycles is vertex-magic.


A. Kotzig and A. Rosa, Magic Valuations of Finite Graphs. Canad. Math. Bull. 13(1970), 451-461.

KAREN MEAGHER, University of Regina, Regina, SK S4S 0A4
Using algebraic graph theory to solve problems in design theory

In this talk I will give a number of examples of a problem in design theory that can be rephrased as a question about a graph. For all of these examples, bounds on the size of a design can be found from an eigenvalue bound from the appropriate graph. The problems I am particularly interested in are related to the Erdös-Ko-Rado theorem. This theorem gives an upper bound on the size of an intersecting set system and describes exactly which systems meet this bound. There are a surprising number of extensions of this famous theorem where the bound can be found using eigenvalue bounds on an appropriate graph.

WENDY MYRVOLD, Dept. of Computer Science, University of Victoria
Finding Independent Sets of a Graph

An independent set of a graph G is a set of vertices of G which are pairwise non-adjacent. There are many applications for which the input is a graph G with a large symmetry group and the goal is to generate either all of the independent sets or all of the maximum independent sets up to isomorphism. We present a very fast practical algorithm for this problem. The tactic can also be applied to many other problems: some examples are generation of all colourings or matchings of a graph up to isomorphism.

This is joint work with Patrick Fowler.

HAMED SHIRAZI, University of Waterloo, 200 University Ave. West, Waterloo, ON N2L 3G1
Equiangular lines and abelian covers of complete graphs

A set of lines in Rn (or Cn) is said to be equiangular if the inner product of every pair of them has the same absolute value. An equiangular set of lines in d real (complex) dimensions has size at most \binomd+12 (d2 in the complex case). Few results are known about the existence of a set of equiangular lines of maximum size.

A graph X is a cover of another graph Y if for each vertex of Y there is an independent set associated with it in X, and each edge in Y is represented by a perfect matching between the respective independent sets in X.

Each antipodal distance-regular cover of a complete graph is determined by three parameters. There are many conditions that these three parameters have to satisfy. We will see that we can find a set of equiangular lines for each abelian cover. This relation between equiangular lines and abelian covers leads to new feasibility conditions for the parameters of the cover. In particular the existence of an antipodal distance-regular cover with certain parameters guarantees the existence of a set of equiangular lines of maximum size.

CLAUDE TARDIF, Royal Military College of Canada, PO Box 17000, Station "Forces", Kingston, Ontario K7K 7B4, Canada
Hedentiemi's conjecture, 40 years later

The categorical product G ×H of two graphs G and H is the graph with vertex set V(G) ×V(H), where two vertices (u,u¢) and (v,v¢) are adjacent if and only if u, v are adjacent in G and u¢, v¢ are adjacent in H. The chromatic number of a categorical product of graphs is the object of a long-standing conjecture:

Conjecture (Hedetniemi 1966): c(G×H) = min{c(G), c(H)}.

The formula is attractive, and holds for many classes of graphs. However, not much is known for the general case, and the conjecture has many doubters. In particular, Poljak and Rödl (1981) defined the following function f:

f(n) = min
{c(G×H) : c(G) = c(H) = n}.
One weaker form of Hedetniemi's conjecture is that the function f is unbounded. For now, all that is known is that if f is bounded, then the upper bound is between 4 and 9.

In this talk, I will explain what is interesting about this conditional result, and what happens when we try to improve it.