 français conference home canadam home

Computational combinatorics
Org: Jan Goedgebeur (Ghent University) and Torsten MĂĽtze (TU Berlin)
[PDF]

RICHARD BREWSTER, Thompson Rivers University
Computational examples for aiding graph theory research  [PDF]

We examine projects where computational tools played a role in generating key examples. Furthermore, the computational techniques turned out to be useful tools for aiding undergraduate research students. We consider two problem areas. The first is graph homomorphisms. An $H$-recolouring sequence of $G$ is a sequence of homomorphisms $G \to H$ where successive mappings differ on a single vertex. Examples computed by Jon Noel led to a series of papers on circular recolouring problems. The second area is broadcast domination and its dual multipacking. The speaker's explorations with Sage have led to new results regarding grids.

JAN GOEDGEBEUR, Ghent University
Generation of hypohamiltonian graphs  [PDF]

We will present a new algorithm to generate all non-isomorphic hypohamiltonian graphs of a given order. (A graph $G$ is hypohamiltonian if $G$ is non-hamiltonian and $G - v$ is hamiltonian for every $v \in V(G)$).

Using this algorithm, we were able to generate complete lists of hypohamiltonian graphs of much larger orders than what was previously possible. This allowed us amongst others to find the smallest hypohamiltonian graph of girth 6 and to show that the smallest planar hypohamiltonian graph has order at least 23.

This is joint work with Carol Zamfirescu.

GARY MACGILLIVRAY, University of Victoria
Hamiltonicity of Bell and Stirling colour graphs  [PDF]

The $k$-Bell colour graph of a graph $G$ has as vertices the partitions of $V(G)$ into at most $k$ independent sets, with $\Pi$ and $\Lambda$ being adjacent if there exists $x$ such that $\Pi_{|_{V(G)-x}} = \Lambda_{|_{V(G)-x}}$. The $k$-Stirling colour graph of $G$ is defined similarly for partitions into exactly $k$ independent sets.

We show that if $V(G)| = n$, then the $n$-Bell colour graph of $G$ is Hamiltonian unless $G \cong K_n, K_n-e$. We also show that for $k \geq 4$, the $k$-Stirling colour graph of a tree with at least $k+1$ vertices is Hamiltonian.

STANISLAW RADZISZOWSKI, Rochester Institute of Technology
Chromatic vertex Folkman numbers, general Folkman problems, and related computational challenges  [PDF]

Graph $G$ (vertex/edge)-arrows graphs $H_1, \dots, H_k$ if every $k$-coloring of its (vertices/edges) contains a monochromatic copy of $H_i$, in some color $i$. A branch of Ramsey theory concerning properties of this arrowing for $F$-free $G$, for some graphs $F$, leads to Folkman-type problems and numbers. Graph $G$ sometimes meets exactly the best bound on its chromatic number. We present some results on the existence of such graphs and related bounds on Folkman numbers, which often lead to computational challenges. We also summarize what was accomplished computationally, and what not, for similar but more general Folkman problems.