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

Graph Theory: Cycles

ALEWYN BURGER, Stellenbosch University
An infinite family of Planar Hypohamiltonian Oriented Graphs  [PDF]

Carsten Thomassen asked in 1976 whether there exists a planar hypohamiltonian oriented graph. We answer his question by presenting an infinite family of planar hypohamiltonian oriented graphs, the smallest of which has order 9. We also show 9 is the smallest possible order of a hypohamiltonian oriented graph.

DARYL FUNK, Simon Fraser University
On the hamiltonicity of line graphs of locally finite, 6-edge-connected graphs  [PDF]

Diestel and Kuhn's construction of the cycle space of an infinite graph has enabled several results on Hamilton cycles in finite graphs to be extended to locally finite graphs. We consider the result that the line graph of a finite 4-edge-connected graph is hamiltonian. We prove a weaker version of this result for infinite graphs: The line graph of locally finite, 6-edge-connected graph with a finite number of thin ends is hamiltonian.

BERT HARTNELL, Saint Mary's University
Decycling in the Cartesian Product  [PDF]

The decycling number of a graph is the minimum number of vertices that must be removed so that the resulting graph is a forest. In an earlier investigation we considered the cartesian product of a graph with a complete graph of order 3 or more and its decycling number. Here we focus on a similar problem but when the complete graph is of order 2. This is joint work with C. Whitehead.

TOMAS KAISER, University of West Bohemia, Pilsen, Czech Republic
Covering a graph by forests and a matching  [PDF]

The fractional arboricity $\Upsilon_f(G)$ of a graph $G$ is a rational relaxation of arboricity introduced by Charles Payan. By a result of Montassier et al., if $\Upsilon_f(G) \leq \tfrac43$, then the edges of $G$ can be covered by a forest and a matching. In this talk, we show that if $\Upsilon_f(G) \leq k+\tfrac1{3k+2}$, then $E(G)$ can be covered by $k$ forests and a matching. Joint work with Mickaël Montassier and André Raspaud.

KHALED SALEM, The British University in Egypt
A characterization of 1-cycle resonant graphs among bipartite 2-connected plane graphs  [PDF]

A graph $G$ is said to be {\em $1$-cycle resonant} if the graph $G$ contains a cycle and every cycle in $G$ is alternating. It is proved that a bipartite 2-connected plane graph $G$ in which the common boundary of adjacent faces is a simple curve is 1-cycle resonant if and only if the outer face of $G$ is alternating and each inner vertex has degree two.

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