CanaDAM 2021
En ligne, 25 - 28 mai 2021


ALBERTO ESPUNY DÍAZ, Technische Universität Ilmenau
Hamiltonicity of randomly perturbed graphs  [PDF]

The study of randomly perturbed graphs has received a lot of attention in recent years. In this area, we consider the union of a dense deterministic graph $H$ (usually with some minimum degree condition) and a random graph $G$, and the main goal is to improve threshold results for random graphs by considering the union with $H$: there are many results showing that, in order for $H\cup G_{n,p}$ to satisfy a given property $\mathcal{P}$, the minimum $p$ which is required is substantially smaller than that required for $G_{n,p}$ itself.

In this talk, I will introduce the model of randomly perturbed graphs and some of the results that have been obtained so far, and then I will present some new results about Hamiltonicity and pancyclicity when we let $G$ be a random regular graph or a random geometric graph. Parts of this are joint work with António Girão.

JAN GOEDGEBEUR, Ghent University
Graphs with few hamiltonian cycles  [PDF]

We will present a new algorithm for the exhaustive generation of all non-isomorphic graphs with a given number $k \ge 0$ of hamiltonian cycles, which is especially efficient for small values of $k$. Our main findings, combining applications of this algorithm and existing algorithms with new theoretical results, revolve around graphs containing exactly one hamiltonian cycle -- i.e. uniquely hamiltonian (UH) graphs -- or exactly three hamiltonian cycles.

In particular, we proved equivalent formulations of the conjecture of Bondy and Jackson that every planar UH graph contains at least two vertices of degree 2, verify it up to order 16, and show that its toric analogue does not hold. We also strengthened a theorem of Entringer and Swart and made progress on conjectures of Sheehan and Cantoni, and answered a question of Chia and Thomassen.

This is joint work with Barbara Meersman and Carol T. Zamfirescu.

RADEK HUŠEK, Charles University, Czech Republic
Counting Circuit Double Covers  [PDF]

Several recent results and conjectures study counting versions of classical existence statements. We ask the same question for cycle double covers of cubic graphs. We show that counting cycle double covers usually allows ``cheating'' by splitting a cycle consisting of more circuits into many cycles, and for this reason we try to count circuit double covers instead. In 2017 we showed that bridgeless cubic planar graphs has $2^{\Omega(\sqrt{n})}$ circuit double covers.

Now we present an exponential bound: Every bridgeless cubic planar graph with $n$ vertices has at least $(5/2)^{n/4 - 1/2}$ circuit double covers. The method we used to obtain this bound motivates a general framework for counting objects on graphs using linear algebra which might be of independent interest. We also conjecture that every bridgeless cubic graph has at least $2^{n/2-1}$ circuit double covers.

CRAIG LARSON, Virginia Commonwealth University
Deming Decompositions and Egervary Graphs  [PDF]

K\"onig-Egerv\'ary (KE) graphs are a generalization of bipartite graphs. Here we discuss Egerv\'ary graphs, which are a generalization of KE graphs and maintain certain attractive properties. A graph is Egerv\'ary if it cannot covered by a matching and a positive even number of odd cycles.

We have extended Deming's KE-recognition algorithm to produce a decomposition of any graph with a perfect matching into subgraphs which are either almost KE (and where $\alpha=\nu-1$) and where the the remaining subgraph is KE (and where $\alpha=\nu$). Each of the subgraphs has a perfect matching. We apply this Deming Decomposition to the investigation of the structure of Egerv\'ary graphs.

This is joint work with Jack Edmonds and Mark Kayll.

CAROL T. ZAMFIRESCU, Ghent University, Belgium
$K_2$-hamiltonian graphs  [PDF]

Motivated by a conjecture of Grünbaum and a problem of Katona, Kostochka, Pach, and Stechkin, both dealing with non-hamiltonian $n$-vertex graphs and their $(n-2)$-cycles, we investigate {\it $K_2$-hamiltonian} graphs, i.e.\ graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph. In the talk we shall present infinitely many cubic non-hamiltonian $K_2$-hamiltonian graphs, both of the 3-edge-colourable and the non-3-edge-colourable variety. In fact, cubic $K_2$-hamiltonian graphs with chromatic index 4 (such as Petersen's graph) are a subset of the critical snarks. We also describe an operation conserving $K_2$-hamiltonicity which yields an infinite family of non-hamiltonian $K_2$-hamiltonian graphs in which, asymptotically, a quarter of vertices has the property that removing such a vertex yields a non-hamiltonian graph, and extend a celebrated result of Tutte by showing that every planar $K_2$-hamiltonian graph with minimum degree at least 4 is hamiltonian.