CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013

Graph Theory II
Chair: Mark Ellingham (Vanderbilt University)

MARK ELLINGHAM, Vanderbilt University
Hamiltonicity of 3-connected planar graphs with a forbidden minor  [PDF] [SLIDES]

Tutte showed in 1956 that all $4$-connected planar graphs are hamiltonian. But examples of $3$-connected planar graphs (or even more specifically, triangulations) that are not hamiltonian have been known since at least the 1930s. So we may ask what additional conditions can be imposed on $3$-connected planar graphs to make them hamiltonian. We show that $K_{2,5}$-minor-free $3$-connected planar graphs are hamiltonian.

This is joint work with Emily Marshall, Kenta Ozeki and Shoichi Tsuchiya.

JAN FONIOK, Queen's University
Right adjoints of Pultr functors  [PDF]

I will talk about recent results of joint work with Claude Tardif about right adjoints of Pultr functors. Constructions, nonexistence results, and applications will be presented. I apologise but a more informative abstract is not possible within the 100-word limit.

NISHAD KOTHARI, University of Waterloo
Characterizing prism-free planar bricks.  [PDF] [SLIDES]

A $3$-connected graph $G$ is a brick if for any two vertices $u$ and $v$, $G-\{u,v\}$ has a perfect matching. Lov{\'a}sz showed that any brick contains either $K_4$ or the prism $\overline{C_6}$ as a conformal minor. A prism-free brick is a brick which does not contain the prism as a conformal minor. We show that the only prism-free planar bricks are the odd wheels, odd staircases and an exceptional graph on ten vertices. This implies a result of Carvalho, Lucchesi and Murty: odd wheels are the only solid planar bricks. Our characterization extends to prism-free planar matching covered graphs.

STEVEN SCHLUCHTER, George Washington University
Ordinary voltage graphs, pseudosurfaces, and derived cellular homology.  [PDF]

Ordinary voltage graph imbeddings provide a way to combinbatorially encode regular (branched) coverings of cellular 2-complexes. While it is somewhat easy to determine up to homeomorphism what the covering space is, it is far more difficult to predict the imbedding of the resulting graph in the covering space. We will survey our recent results which partially describe the graph imbedding in the covering space in terms of cellular homology.

ÁGNES TÓTH, Alfréd Rényi Institute of Mathematics, Budapest
The asymptotic value of the independence ratio for the direct graph power  [PDF] [SLIDES]

The independence ratio, $i(G)$ of a graph $G$ is the ratio of the independence number and the vertex number. Its asymptotic value for the direct power is $A(G)=\lim_{k\to\infty}i(G^{\times k})$, where $G^{\times k}$ denotes the $k$th direct power of $G$. In the talk I will show that $A(G)$ can be calculated from the ratios of the size of the independent sets of $G$ and the size of their neighbourhoods, giving the answer for a question of Alon and Lubetzky. It also proves the conjecture of Brown, Nowakowski and Rall stating that $A(G+H)=\max\{A(G),A(H)\}$, where $G+H$ denotes the disjoint union of the graphs.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Memorial University of Newfoundland