2020 CMS Winter Meeting

Montreal, December 4 - 7, 2020

Abstract Submission Form Plenary, Prize and Public Lectures By session By speaker Posters

Graph Theory
Org: Danielle Cox (Mount Saint Vincent University), Kyle Mackeigan (Dalhousie University) and Todd Mullen (University of Saskatchewan)
[PDF]

AHMAD ALKASASBEH, Memorial University of Newfoundland Graceful Labellings of Variable Windmills Using Skolem Sequences [PDF]

A windmill is a graph obtained by identifying a set of graphs (the "vanes") at a single common vertex. In this work, we introduce graceful and near graceful labellings of several families of windmills. In particular, we use Skolem-like sequences to prove (near) graceful labellings exist for all possible windmills with $C_{3}$ and $C_{4}$ vanes, and infinite families of 3,5-windmills and 3,6-windmills.

Joint work with Danny Dyer and Jared Howell.

ROBERT BAILEY, Grenfell Campus, MUN On the 486-vertex distance-regular graphs of Koolen--Riebeek and Soicher [PDF]

In this talk, we consider three imprimitive distance-regular graphs with 486 vertices and diameter 4: the Koolen--Riebeek graph (which is bipartite), the Soicher graph (which is antipodal), and the incidence graph of a symmetric transversal design obtained from the affine geometry $\mathrm{AG}(5,3)$ (which is both). We will show that each of these is preserved by the same rank-9 action of the group $3^5:(2\times M_{10})$, and the connection is explained using the ternary Golay code.

Ths is joint work with Daniel Hawtin (University of Rijeka, Croatia).

IAIN BEATON, Dalhousie University The Average Order of Dominating Sets of a Graph [PDF]

This talk focuses on the average order of dominating sets of a graph. We find the extremal graphs for the maximum and minimum value over all graphs on $n$ vertices, while for trees we prove that the star minimizes the average order of dominating sets. We prove the average order of dominating sets in graphs without isolated vertices is at most $3n/4$, but provide evidence that the actual upper bound is $2n/3$. Finally, we show that the normalized average, while dense in $[1/2,1]$, tends to $\frac{1}{2}$ for almost all graphs. Joint work with Jason Brown.

BEN CAMERON, University of Guelph The mean subtree order of a graph under edge addition [PDF]

For a graph $G$, the mean subtree order is the average order of a subtree of $G$. The mean subtree order was introduced for trees by Jamison in a series of seminal papers in the 1980s. Very recently, Chin, Gordon, MacPhee, and Vincent extended this notion to graphs and conjectured that for every connected graph, adding an edge between any pair of distinct vertices will increase the mean subtree order. In this talk, we show that the conjecture is false by constructing graphs of order $n$ where the addition of a single edge can decrease the mean subtree order by as much as $n/3$ asymptotically. We then amend the original conjecture and prove it in the special case that $G$ is a tree.

(This is joint work with Lucas Mol)

NANCY CLARKE, Acadia University Surrounding Cops and Robber [PDF]

A variation of the Cops and Robber game is introduced in which the cops win by occupying each of the robber's neighbouring vertices. The surrounding copnumber is analogous to the copnumber. We present a variety of results for this parameter, including exact values for several classes of graphs as well as more general bounds. Classes of interest include graph products, graphs arising from combinatorial designs, and generalized Petersen graphs.

This is joint work with A. Burgess, R. Cameron, P. Danziger, S. Finbow, C. Jones, and D. Pike.

CHRIS DUFFY, University of Saskatchewan Homomorphisms to Reflexive Oriented and Edge-Coloured Graphs [PDF]

In the study of graph homomorphisms, the existence of non-trivial homomorphisms to reflexive targets isn’t particularly interesting; if the target has at least one edge between a pair of distinct vertices, such a homomorphism always exists. For oriented and 2-edge-coloured graphs, however, the picture is much more complicated. In this talk we examine non-trivial homomorphism of such graphs to reflexive targets. Among other things we study the structure of such graphs that admit only proper homomorphisms to reflexive targets.

DANNY DYER, Memorial University of Newfoundland Gracefully labelling triangular cacti using Skolem sequences [PDF]

Graceful labelling arose in the context of finding graph decompositions, but has since become an interesting question in its own right. We examine the use of Skolem sequences to gracefully label triangular windmills with pendants, and show there is hope to similarly label triangular snakes. Joint work with Ahmad Alkasasbeh and Nabil Shalaby.

MELISSA HUGGAN, Ryerson University The Orthogonal Colouring Game [PDF]

The Orthogonal Colouring Game is a combinatorial game in which two players alternately colour vertices of a pair of isomorphic graphs while respecting the properness and the orthogonality of the colouring. Each player aims to maximise her score, which is the number of coloured vertices in the copy of the graph she owns.

An involution $\sigma$ of a graph $G$ is strictly matched if its fixed point set induces a clique and any non-fixed point $v\in V(G)$ is connected with its image $\sigma(v)$ by an edge.

In this talk, we introduce the game and our main result that the second player has a strategy to force a draw in this game for graphs that admit a strictly matched involution.

This is joint work with Stephan Dominique Andres, Fionn Mc Inerney, and Richard J. Nowakowski.

JEANNETTE JANSSEN, Dalhousie University Simultaneous embeddings of nested interval graphs [PDF]

A proper interval graph is a graph that has an adjacency matrix which is diagonally increasing: rows and columns are unimodal, with the maximum occurring at the diagonal. It is well-known that proper interval graphs have a unit interval representation: vertices can be embedded in R so that vertices are adjacent if and only if their embedded values are within a threshold distance d from each other. We extend this notion to diagonally increasing (symmetric) matrices that have interval values greater than 1. Such matrices can be written as the sum of adjacency matrices of a nested family of proper interval graphs. we study the question whether it is possible, given a diagonally increasing matrix A, we can find an embedding which is a unit interval representation for all graphs in the nested family simultaneously. This is joint work with Zhiyuan (Owen) Zhang.

KYLE MACKEIGAN, Dalhousie Orthogonal Colourings of Graphs [PDF]

Two colourings of a graph are orthogonal if they have the property that when two vertices have the same colour in one of the colourings, then those vertices must have different colours in the other colours. In this talk, open orthogonal colouring conjectures are answered. Then, orthogonal colourings of tensor and Cartesian product graphs are discussed.

MARGARET-ELLEN MESSINGER, Mount Allison University Reconfiguration for Dominating Sets [PDF]

Given a problem and a set of feasible solutions to that problem, the associated reconfiguration problem involves determining whether one feasible solution to the original problem can be transformed to a different feasible solution through a sequence of allowable moves, with the condition that the intermediate stages are also feasible solutions.

Any reconfiguration problem can be modelled with a reconfiguration graph, where the vertices represent feasible solutions and two vertices are adjacent if and only if the corresponding feasible solutions can be transformed to each other via one allowable move.

Our interest is in reconfiguring dominating sets of graphs. The domination reconfiguration graph of a graph $G$, denoted $\mathcal{D}(G)$, has a vertex corresponding to each dominating set of $G$ and two vertices of $\mathcal{D}(G)$ are adjacent if and only if the corresponding dominating sets differ by the deletion or addition of a single vertex. We are interested in properties of domination reconfiguration graphs. For example, it is easy to see that they are always connected and bipartite. While none has a Hamilton cycle, we explore families of graphs whose reconfiguration graphs have Hamilton paths.

This is joint work with: K. Adaricheva, Hofstra University, C. Bozeman, Mount Holyoke College, N. Clarke, Acadia University, R. Haas, University of Hawaii at Manoa, K. Seyffarth, University of Calgary, and H. Smith, Davidson College

LUCAS MOL, University of Winnipeg The Threshold Dimension of a Graph [PDF]

Let $G$ be a graph. A set of vertices $S$ of $G$ is called a \emph{resolving set} of $G$ if every vertex of $G$ is uniquely determined by its vector of distances to the vertices in $S$. One can think of the vertices in a resolving set as ``landmark'' vertices. If an agent is sitting at some vertex of the graph, and its distance to every landmark vertex is known, then one can determine the exact location of the agent.

Imagine that there is a cost associated with each landmark vertex. Then one would be interested in finding a resolving set of minimum cardinality in $G$; this is the well-studied \emph{metric dimension} of $G$. Imagine further that we can add edges to $G$ in a highly cost effective manner. Then one would be interested in finding a resolving set of minimum cardinality across all graphs $H$ obtained by adding edges to $G$; we introduce this parameter as the \emph{threshold dimension} of $G$.

We give a more geometrical description of those graphs with threshold dimension $b$, characterizing them as graphs that have certain constrained embeddings in the strong product of $b$ paths. We provide a sharp bound on the threshold dimension of $G$ in terms of the chromatic number. We also study \emph{irreducible graphs} -- those for which the threshold dimension is equal to the metric dimension. This is joint work with Matthew Murphy and Ortrud Oellermann.

TODD MULLEN, University of Saskatchewan Recent Results in Diffusion [PDF]

Diffusion is a variant of Chip-Firing in which every vertex sends a chip to each of its poorer neighbours at every time step. Duffy et al. conjectured in the original paper on the topic (2018) that Diffusion is always a periodic process with only periods of length 1 and 2. This was proven by Long and Narayanan (2019). We discuss recent work on this model, some of which arose from Long and Narayanan's proof. This work includes the number of unique configurations that exist on paths and complete graphs up to a definition of equality and some different period lengths that arise from altering the firing rules. This is joint work with Richard Nowakowski (Dalhousie) and Danielle Cox (MSVU).

top of page