
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 timesteps. A firefighter saves one vertex in each timestep 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 timestep. 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 inneighbours of a vertex receive the same colour and no two outneighbours 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 pointline incidence graphs of finite projective planes and graphs by the CaiFurerImmerman 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 nonisomorphic graphs tested. It is known that the WeisfeilerLehman 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 kdimensional WeisfeilerLehman 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 kdim WL refinement.
There is some interest in graphs with the characteristic that the greedy algorithm produces a set with a desired property efficiently. For example, wellcovered 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 wellcovered graphs of girth 8 or more can be described essentially the same as the wellcovered trees. A number of problems of this type will be outlined.
Let ν(G) denote the maximum number of edgedisjoint 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_{4} we have ν(K_{4})=1 and τ(K_{4})=2. We prove that for every planar graph G with no K_{4}, τ(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 edgedisjoint K_{4}subgraphs plus 10x additional edgedisjoint triangles.
This represents joint work with A. Kostochka and S. Thomassé.
The Georges graph is a bipartite, nonhamiltonian, 3connected, 3regular graph on 50 vertices with girth 6. An n_{3} 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_{3} configuration, called the Georges configuration, introduced by Grunbaum. An n_{3} 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_{3} configuration has a coordinatization. Grunbaum has conjectured that an n_{3} 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 wellknown 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 selfstabilizing 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 iblockintersection graph of D is the graph G_{i}(D) having vertex set B such that two vertices b_{1} and b_{2} are adjacent in G_{i}(D) if and only if b_{1} ∩b_{2}  = i. It has been known since 1999 that the 1blockintersection graph of any λfold triple system on v ≥ 12 points is Hamiltonian. We now show that the 1blockintersection 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.
We extend the study of the nexistential closure property of block intersection graphs (BIGs) of designs to infinite designs. An infinite design is a design with an infinite number of points while k, t and λ can be either finite or infinite.
If λ = 1 we show that the BIG of an infinite design is ne.c. if and only if n ≤ min{t,[(k−1)/(t−1)] +1}. If λ ≥ 2, then the BIG of a design is 2e.c., it is not ne.c. for any n ≥ min{t+1,[(k)/(t)] +1}, and it is not necessarily 3e.c. Our results show that BIGs of infinite designs with finite k and λ are different from countably infinite random graphs; countably infinite random graphs are ne.c for any positive integer n, while n is bounded for the nexistential closure property of the BIGs of infinite designs.
This is joint work with David A. Pike (email: dapike@mun.ca).