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.

The complete equipartite graph K_m *[`(K<sub>n</sub>)] 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 K<sub>m</sub> and K<sub>m</sub> *[`(K₂)] 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 K_m *[`(K<sub>n</sub>)] 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 K<sub>m</sub> *[`(K_n)] into closed trails of length k.

This is joint work with Mateja Sajna.

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.

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

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

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.

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.

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.

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.

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.

References

[1]

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

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.

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.

A set of lines in Rⁿ (or Cⁿ) 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 (d² 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.