 français conference home canadam home

Cycles in Planar Graphs
Org: Abhinav Shantanam (Simon Fraser University) and Carol T. Zamfirescu (Ghent University)
[PDF]

XIAONAN LIU, Georgia Institute of Technology
Number of Hamiltonian cycles in planar triangulations  [PDF]

Hakimi, Schmeichel, and Thomassen conjectured in 1979 that if $G$ is a 4-connected planar triangulation with $n$ vertices then $G$ contains at least $2(n-2)(n-4)$ Hamiltonian cycles, with equality if and only if $G$ is a double wheel. Alahmadi, Aldred, and Thomassen recently proved that there are exponentially many Hamiltonian cycles in 5-connected planar triangulations. We consider 4-connected planar $n$-vertex triangulations $G$ that do not have too many separating 4-cycles or have minimum degree 5. We show that if $G$ has $O(n/{\log}_2 n)$ separating 4-cycles then $G$ has $\Omega(n^2)$ Hamiltonian cycles, and if $\delta(G)\ge 5$ then $G$ has $2^{\Omega(n^{1/4})}$ Hamiltonian cycles.

ON-HEI SOLOMON LO, University of Science and Technology of China
Gaps in the cycle spectrum of polyhedral graphs  [PDF]

It was recently initiated by Merker to study whether every polyhedral graph must have a cycle length in some certain integer interval. For any positive integer $k$, define $f(k)$ (respectively, $f_3(k)$) to be the minimum integer $\ge k$ such that every 3-connected planar graph (respectively, 3-connected cubic planar graph) of circumference $\ge k$ has a cycle whose length is in the interval $[k,f(k)]$ (respectively, $[k,f_3(k)]$). We will describe how the values of $f(k)$ and $f_3(k)$ can be determined. This is a joint work with Qing Cui.

Hamiltonicity of planar graphs with a forbidden minor  [PDF]

Tutte proved that all $4$-connected planar graphs are Hamiltonian, but it is well-known that $3$-connected planar graphs are not necessarily Hamiltonian. In this talk, we discuss the Hamiltonicity of certain $3$-connected planar graphs with forbidden minors.

JENS M. SCHMIDT, Hamburg University of Technology
The Isolation Lemma  [PDF]

A cycle $C$ of a graph $G$ is \emph{isolating} if every component of $G-V(C)$ consists of a single vertex. We show that isolating cycles in polyhedral graphs can be extended to larger ones: every isolating cycle $C$ of length $6 \leq |E(C)| < \left \lfloor \frac{2}{3}(|V(G)|+4) \right \rfloor$ implies an isolating cycle $C'$ of larger length that contains $V(C)$. By hopping'' iteratively to such larger cycles, we obtain a powerful and very general inductive motor for proving long cycles and computing them (in quadratic runtime).

This is joint work with Jan Kessler.

ABHINAV SHANTANAM, Simon Fraser University
Pancyclicity in $4$-connected planar graphs  [PDF]

A graph on $n$ vertices is said to be pancyclic if, for each $k \in \{3,...,n\}$, it contains a cycle of length $k$. Following Bondy's meta-conjecture that almost any nontrivial condition on a graph which implies Hamiltonicity also implies pancyclicity, Malkevitch conjectured that a $4$-connected planar graph is pancyclic if it contains a cycle of length $4$. We show that, for any edge $e$ in a $4$-connected planar graph $G$, there exist at least $\lambda(n-2)$ cycles of pairwise distinct lengths containing $e$, where $\lambda=5/12$. We also show that $\lambda$ can be $2/3$ at best. Joint work with Bojan Mohar.