CanaDAM 2015
University of Saskatchewan, June 1 - 4, 2015

Cycles in graphs I
Organizer and Chair: David Gunderson (University of Manitoba) and Ortrud Oellermann (University of Winnipeg)

DAVID BROWN, Utah State University
Chordal Graphs aren’t Cycle Extendable … So What?  [PDF]

A cycle in a graph is extendable if its vertices are contained in a cycle of size one greater. A graph is cycle extendable if every non-Hamiltonian cycle is extendable. Hendry conjectured that any Hamiltonian chordal graph is cycle extendable. This conjecture was proven for several subclasses of chordal graphs such as interval graphs, split graphs, and spider intersection graphs. But Hendry’s conjecture has been disproved (Lafond, Seamone, 2014+). I’ll give another conjecture to replace Hendry’s which will hopefully inspire some more nice papers, and share some results on tournaments and their cycle extendability.

This talk will be presented by Andrii Arman.

DAVID GUNDERSON, University of Manitoba
Forbidding an odd cycle, extremal numbers and extremal graphs  [PDF]

For a simple graph $G$ on $n$ vertices, and a cycle $C$ of odd length, how many edges can $G$ have while not containing a copy of $C$ as a subgraph and what does such an "extremal" graph look like? Bondy and Woodall found, for all but finitely many $n$, the number of edges in an extremal $C$-free graph. Their proof did not reveal what the extremal graphs are. Simonovits proved that for sufficiently large $n$, such an extremal graph is unique. In recent work with Furedi, all remaining extremal numbers and extremal graphs for odd cycles are found.

ORTRUD OELLERMANN, University of Winnipeg
Cycle Structure in Graphs with Certain Local Properties  [PDF]

A graphs is weakly pancyclic if it has a cycle of every length between the girth and the circumference. A graph is locally $P$ for some graph property $P$ if the subgraph induced by the open neighbourhood of every vertex has property $P$. Ryjacek conjectured that every locally connected graph is weakly pancyclic. Results in support of this conjecture for locally isometric graphs and locally connected graphs with sufficiently large minimum clustering coefficient are presented. It is shown that in many instances these graphs are cycle extendable. Related open problems are discussed.

BEN SEAMONE, Dawson College
Hendry's Conjecture: counterexamples and new open problems  [PDF]

Let $G$ be a graph $G$ of order $n$. If the vertices of any (non-Hamiltonian) cycle $C$ are contained in a cycle of length one greater, $G$ is cycle extendable. Hendry conjectured that every chordal graph containing a Hamiltonian cycle is cycle extendable. We disprove this conjecture with an infinite family of graphs. We discuss additional properties one may require in order for the original conjecture to hold and present several open questions (and partial solutions) involving strongly chordal graphs, induced subgraphs, connectivity and toughness, intersection models, and graph density. Joint with Manuel Lafond (Universit\'e de Montr\'eal).

SERGEI TSATURIAN, University of Manitoba
Triangle-free graphs with the maximum number of cycles  [PDF]

In a recent article by Durocher, Gunderson, Li, and Skala, it was asked which triangle-free graphs contain the maximum number of cycles; this question arose from the study of path-finding algorithms. The same authors conjectured that for each $n\geq 4$, the balanced complete bipartite graph contains more cycles than any other $n$-vertex triangle-free graph. In recent work with Arman and Gunderson, we prove this conjecture for $n\geq 141$. This result and possible generalizations are discussed.

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 University of Saskatchewan