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 4connected planar triangulation with $n$ vertices then $G$ contains at least $2(n2)(n4)$ 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
5connected planar triangulations. We consider 4connected planar $n$vertex triangulations $G$ that do not have too many separating 4cycles or have minimum degree 5. We show that if $G$ has $O(n/{\log}_2 n)$ separating 4cycles then $G$ has $\Omega(n^2)$ Hamiltonian cycles, and if $\delta(G)\ge 5$ then $G$ has $2^{\Omega(n^{1/4})}$ Hamiltonian cycles.
 ONHEI 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 3connected planar graph (respectively, 3connected 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.
 EMILY A. MARSHALL, Arcadia University
Hamiltonicity of planar graphs with a forbidden minor [PDF]

Tutte proved that all $4$connected planar graphs are Hamiltonian, but it is wellknown 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 $GV(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 metaconjecture 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(n2)$ 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.