CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Graph Theory I

RICHARD BREWSTER, Thompson Rivers University
Lexicographic products with high reconstruction number  [PDF]

The \emph{reconstruction number} of a graph is the smallest number of vertex deleted subgraphs needed to uniquely determine the graph up to isomorphism. Almost all graphs have reconstruction number three. We use lexicographic products of vertex transitive graphs with certain starter graphs to generate new infinite families of graphs with \emph{high reconstruction numbers} (i.e. greater than three), settling a question of McMullen and Radziszowski. Joint with Ge\v{n}a Hahn, Stacey Lamont, and Chester Lipka.

DENNIS D.A. EPPLE, University of Victoria
Covering lexicographic products of graphs with independent sets and cliques  [PDF]

A graph is $(k,l)$-colourable, if its vertex set can be covered by $k$ independent sets and $l$-cliques. Two variants of the chromatic number that arise from this concept are the cochromatic number and the bichromatic number. We will investigate the behaviour of these graph invariants for the lexicographic product of graphs, establish some general bounds and give some precise results for a few interesting cases.

TERRY MCKEE, Wright State University
Graphs that have clique (partial) 2-trees  [PDF]

Much of the theory---and the applicability---of chordal graphs is based on their having clique trees. Chordal graphs can be generalized to the graphs that have clique representations that are 2-trees, or even series-parallel graphs (partial 2-trees) or outerplanar or maximal outerplanar graphs. The resulting graph classes can be characterized by forbidding edge contractions of a few induced subgraphs. There is also a plausible application of such graphs to systems biology.

BODE MICHEL, Otto-von-Guericke-Universität Magdeburg
Good edge labelings of graphs of average degree at most 3  [PDF]

An edge labeling of a graph is called good, if for every ordered pair of distinct vertices $(u,v)$ there is at most one nondecreasing path from $u$ to $v$. Araújo, Cohen, Giroire and Havet conjecture that every $K_3$- and $K_{2,3}$-free graph of average degree $\leq3$ has a good labeling. This talk reports on progress towards this conjecture. In particular, a proof is given for the special case when the girth is at least 5.

K. B. REID, California State University San Marcos
Landau's Theorem Revisited Again  [PDF]

We describe a new proof of Landau's theorem giving necessary and sufficient conditions for a nondecreasing sequence of n integers to be the score sequence for some n-tournament. Given a nondecreasing sequence S of n integers that satisfies Landau's conditions, our proof can be used to construct an n-tournament with score sequence S. This work is joint with Michael Santana.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria