The Firefighter Problem is a simplified model for the spread of a fire (or disease or computer virus) in a network. A fire breaks out at a vertex in a connected graph, and spreads to its neighbours over discrete time-steps. A firefighter saves one vertex in each time-step which is not yet burned. Since its introduction by Hartnell in 1995, there is a steadily growing corpus of both structural and algorithmic results on the Firefighter problem.

While maximizing the number of saved vertices usually requires a strategy on the part of the firefighter, the fire itself spreads without any strategy. Consider a variant of the problem where the fire is intelligent but burns slowly. For a fixed positive integer k, the fire chooses to burn at most k unsaved neighbours in a given time-step. The surviving rate of G is defined as the expected percentage of vertices that can be saved when a fire breaks out at a random vertex of G.

Using spectral techniques, we establish asymptotic bounds on the surviving rate for random regular graphs. We consider the limiting survival rate for countably infinite graphs. In particular, we show that the limiting survival rate of the infinite random graph can be any real number in [0,1].

The reconstruction number of a graph is the smallest number of vertex deleted subgraphs needed to uniquely determine the graph up to isomorphism. Bollobas proved that almost all graphs have reconstruction number three. McMullen and Radziszowski have published a catologue of all graphs on at most ten vertices with reconstruction number greater than three, i.e., graphs with high reconstruction number. We introduce constructions that generalize the examples identified in their work. In particular, we use lexicographic products of vertex transitive graphs with certain starter graphs from the work of Harary and Plantholt to generate new infinite families of graphs with high reconstruction numbers. In the process, we settle a question of McMullen and Radziszowski.

This is joint work with Gena Hahn, Stacey Lamont, and Chester Lipka.

An emphoriented colouring of an oriented graph G is a colouring of the vertices of G with the property that if there exists an edge of G joining a vertex of colour i to a vertex of colour j, i ≠ j, then no edge of G joins a vertex of colour j to a vertex of colour i. There are several possible definitions of an injective oriented colouring of G. One choice requires that no two in-neighbours of a vertex receive the same colour and no two out-neighbours receive the same colour. We study these colourings and the injective oriented chromatic number (primarily in the proper case) in terms of complexity, obstructions, critical graphs, cliques, products, and bounds.

The computational complexity of graph isomorphism has remained unresolved for decades. Research is conducted on the complexity of the problem in general, and usually efficient algorithms on restricted graph classes are designed. Although, it is not easy to devise difficult graph isomorphism instances, combinatorial constructions have provided the most difficult, notably point-line incidence graphs of finite projective planes and graphs by the -Cai-Furer-Immerman construction.

In this talk, we show a novel approach for a polynomial time Graph Isomorphism tester. The key part of this scheme produces labelled trees (which are invariant), by decomposing the given graphs via a particular ordering. To date, the GI tester has not failed to distinguish any non-isomorphic graphs tested. It is known that the Weisfeiler-Lehman algorithm subsumes almost all combinatorial graph algorithms that are not based on group theoretic methods. It is also true that for any fixed k, the k-dimensional Weisfeiler-Lehman algorithm solves graph isomorphism only for a subclass of graphs. It has not been determined if the GI tester using the labelled cycle decomposition tree scheme is subsumed by some k-dim W-L refinement.

There is some interest in graphs with the characteristic that the greedy algorithm produces a set with a desired property efficiently. For example, well-covered graphs (every maximal independent set of vertices is of one size and, hence, maximum) fall into this category. Many such problems have the rather curious feature that if one knows the structure of trees in the collection, then this characterization is essentially the same even with cycles present as long as they are not too small. For instance, the well-covered graphs of girth 8 or more can be described essentially the same as the well-covered trees. A number of problems of this type will be outlined.

Let ν(G) denote the maximum number of edge-disjoint triangles in a graph G and τ(G) denote the minimum number of edges covering all triangles of G. An old conjecture of Tuza states that τ(G) ≤ 2ν(G) for every graph G. Tuza proved that his conjecture holds for planar graphs, and the result is sharp, since for the graph K₄ we have ν(K₄)=1 and τ(K₄)=2. We prove that for every planar graph G with no K₄, τ(G) ≤ 1.5ν(G), and this result is also sharp.

Let τ^*(G) denote the minimum total weight of a fractional covering of its triangles by edges. Krivelevich proved the fractional version of Tuza's conjecture, that τ^*(G) ≤ 2ν(G) for every graph G. We give a stability version of this result by showing that if a graph G has τ^*(G) ≥ 2ν(G)−x, then G contains ν(G)− 10x  edge-disjoint K₄-subgraphs plus 10x  additional edge-disjoint triangles.

This represents joint work with A. Kostochka and S. Thomassé.

The Georges graph is a bipartite, non-hamiltonian, 3-connected, 3-regular graph on 50 vertices with girth 6. An n₃ configuration consists of a set of n points and n lines such that each line is incident on 3 points, and each point is incident on 3 lines. The Georges graph can be viewed as the incidence graph of a 25₃ configuration, called the Georges configuration, introduced by Grunbaum. An n₃ configuration has a coordinatization over a field K, if the points can be assigned coordinates (x,y), where x and y are in K, such that the lines are then given by linear equations.

In general, it is difficult to determine whether a given n₃ configuration has a coordinatization. Grunbaum has conjectured that an n₃ configuration which has a coordinatization over the reals also has a coordinatization over the rationals. Recently he proved that the Georges configuration has a coordinatization over the reals. I have since found a rational coordinatization of the Georges configuration. The method of constructing a coordinatizing polynomial and its application to the Georges configuration will be presented.

The chromatic index χ′ of a multigraph G is the minimum number of colours needed to colour the edges of G such that no two edges sharing a vertex have the same colour. There are many well-known upper bounds for χ′, including bounds by Shannon, Vizing, Goldberg and Steffen. In this talk we explore the question of which multigraphs actually achieve these bounds. As part of the discussion we present a new partial characterization of those multigraphs achieving Vizing's upper bound, a result obtained jointly with P. Haxell.

Imagine a large building with many corridors. A robot cleans these corridors in a greedy fashion: the next corridor cleaned is always the dirtiest to which it is incident. We let s(G) and S(G) denote the minimum and maximum number of time steps (over all edge weightings) before every edge of a graph G has been cleaned and determine bounds on both s(G) and S(G). We also show that Eulerian graphs have a self-stabilizing property that holds for any initial edge weighting: after the initial cleaning of all edges, all subsequent cleanings require s(G) time steps.

Given a BIBD(v,k,λ), D say, with λ > 1 and having block set B, the i-block-intersection graph of D is the graph G_i(D) having vertex set B such that two vertices b₁ and b₂ are adjacent in G_i(D) if and only if |b₁ ∩b₂ | = i. It has been known since 1999 that the 1-block-intersection graph of any λ-fold triple system on v ≥ 12 points is Hamiltonian. We now show that the 1-block-intersection graphs of BIBD(v,k,λ) with block size k=4 are Hamiltonian when v is sufficiently large.

This is joint work with Andrew Jesso and Nabil Shalaby of Memorial University of Newfoundland.