2010 CMS Summer Meeting
University of New Brunswick (Fredericton), June 4 - 6, 2010

Graph Theory
Org: Stephen Finbow (St. Francis Xavier) and Shannon Fitzpatrick (UPEI)

ANTHONY BONATO, Ryerson University
Fighting intelligent fires

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].

RICHARD BREWSTER, Thompson Rivers University
Lexicographic Products and High Reconstruction Numbers

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.

NANCY CLARKE, Acadia University, Wolfville, NS B4P 2R6
Injective Oriented Colourings

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, ij, 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.

ART FINBOW, Saint Mary's

ORTHO FLINT, University of Western Ontario
Graph Isomorphism Testing

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.

BERT HARTNELL, Saint Mary's University, Halifax, NS
Girth and the Greedy Algorithm

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.

PENNY HAXELL, University of Waterloo
On covering triangles by edges

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 K4 we have ν(K4)=1 and τ(K4)=2. We prove that for every planar graph G with no K4, τ(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 K4-subgraphs plus 10x  additional edge-disjoint triangles.

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

WILLIAM KOCAY, University of Manitoba
A Rational Coordinatization of the Georges Configuration

The Georges graph is a bipartite, non-hamiltonian, 3-connected, 3-regular graph on 50 vertices with girth 6. An n3 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 253 configuration, called the Georges configuration, introduced by Grunbaum. An n3 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 n3 configuration has a coordinatization. Grunbaum has conjectured that an n3 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.

JESSICA MCDONALD, Simon Fraser University
Extremal multigraphs for edge-colouring

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.

MARGARET-ELLEN MESSINGER, Ryerson University, Toronto, Ontario
Greedily cleaning edges: the robot vacuum

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.

DAVID PIKE, Memorial University of Newfoundland
Hamilton Cycles in 1-Block-Intersection Graphs

Given a BIBD(v,k,λ), D say, with λ > 1 and having block set B, the i-block-intersection graph of D is the graph Gi(D) having vertex set B such that two vertices b1 and b2 are adjacent in Gi(D) if and only if |b1b2 | = 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.

ASIYEH SANAEI, Memorial University of Newfoundland
Existential Closure of Block Intersection Graphs of Infinite Designs

We extend the study of the n-existential 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 n-e.c. if and only if n ≤ min{t,[(k−1)/(t−1)] +1}. If λ ≥ 2, then the BIG of a design is 2-e.c., it is not n-e.c. for any n ≥ min{t+1,[(k)/(t)] +1}, and it is not necessarily 3-e.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 n-e.c for any positive integer n, while n is bounded for the n-existential closure property of the BIGs of infinite designs.

This is joint work with David A. Pike (email:

Event Sponsors

AARMS: Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences

© Canadian Mathematical Society :