Abstracts

PLENARY SPEAKER ABSTRACTS

Vertex partition of planar graphs into forests

Danjun Huang - Department of Mathematics, Zhejiang Normal University, Jinhua, China

Abstract: Let G=(V,E)$ be a graph. For i=1,2,…,k, let $\mathcal{G}_i$ be the classes of graphs. A $(\mathcal{G}_1,\mathcal{G}_2,\ldots,\mathcal{G}_k)$-partition is the partition of V(G) into k subsets V₁,V₂,…,V_k such that G[V_i] belongs to $\mathcal{G}_i$ for all i=1,2,…,k. In particular, we use $\mathcal{F}$, $\mathcal{F}_d$, and $\mathcal{I}$ to denote the class of forests, the class of forests with maximum degree d, and the class of graphs with no edges (independent sets), respectively.

It is well known that every planar graph admits an $(\mathcal{I},\mathcal{I},\mathcal{I},\mathcal{I})$-partition, an $(\mathcal{F},\mathcal{F},\mathcal{F})$-partition, and an $(\mathcal{F}_2,\mathcal{F}_2,\mathcal{F}_2)$-partition. In this talk, we will give a brief survey on the vertex partition of planar graphs into forests. Moreover, we also give some related problems on partitions of graphs.

Matroids viewed as generalized electrical networks

David Wagner - Department of Combinatorics and Optimization, University of Waterloo, Canada

Abstract:

The Matrix-Tree Theorem provides an algebraic link between physical properties of electrical networks and probabilistic properties of random spanning trees of graphs. Much, but not all, of the linear algebra in this story can be abstracted away from graphs, and applied to more general classes of matroids. Some properties can be studied meaningfully even when the linear algebra breaks down completely. This talk is a survey of what is known about the structure of matroids that either do or do not behave in a physically sensible way from this point of view. No familiarity with matroid theory will be assumed.

Changing times in temporal graphs

Jessica Enright -Global Academy of Agriculture and Food Security, University of Edinburgh, Scotland

Abstract: Temporal graphs (in which edges are active only at specified time steps) are an increasingly important and popular model for a wide variety of natural and social phenomena. I'll talk a bit about what's been going on in the world of temporal graphs, and then go on to the idea of graph modification in a temporal setting.

Motivated by cows and rumours, I'll talk about a particular modification problem in which we assign times to edges so as to maximise or minimise reachability sets within a temporal graph. I'll mention an assortment of complexity results on these problems, showing that they are hard under a disappointingly large variety of restrictions. In particular, if edges can be grouped into classes that must be assigned the same time, then the problem is hard even on directed acyclic graphs when both the reachability target and the classes of edges are of constant size, as well as on an extremely restrictive class of trees. For fans of parameterised complexity, I'll note that one version of the problem is W[1]-hard when parameterised by the vertex cover number of the instance graph. The situation is slightly better if each edge is active at a unique timestep - in some very restricted cases the problem is solvable in polynomial time. (Joint work with Kitty Meeks.)

CONTRIBUTED TALKS

Tuesday August 13^th, 2019

Orthogonal colourings of Cayley graphs

Kyle MacKeigan – Dalhousie University

Abstract: Two colourings of a graph are said to be orthogonal if they have the property that, if two elements receive the same colour in one colouring, then they must receive different colours in the second colouring. Orthogonal colourings of Cayley graphs will be discussed.

On distance-regular graphs on 486 vertices

Robert Bailey- Memorial University of Newfoundland, Grenfell Campus

Abstract: A graph is distance-regular if, for any i and any vertices u,v at distance i, the number of neighbours of $v$ at distance $i-1$, $i$ or $i+1$ from $u$ depends only on $i$ and not on the choice of vertices. The {\em Koolen—Riebeek graph} is a particular distance-regular graph on $486$ vertices of degree $45$, which arises from a particular permutation representation of the group $3⁵ : (2xM₁₀). However, this group action also gives rise to several other distance-regular graphs with the same vertex set, some more interesting than others, but this connection had not previously been noticed. We give an explanation using affine geometry and the ternary Golay code. This is joint work with Daniel Hawtin (Rijeka).

Computational Aspects of Closed Dominating Walks and Rescent Results

Jared Howell - Memorial University of Newfoundland, Grenfell Campus

A watchman's walk, in a simple graph G is a minimum closed dominating walk. It can be thought of as an optimal way to move through a graph continuously and see (but not necessarily visit) every vertex. We denote the length of a watchman's walk in G by w(G). In this talk, we will explore some computational results and compare these to similar problems. We will also look at the structure of watchman's walks and results from one of our current projects.

The Watchman's Walk Problem on Directed Graphs

Brittany Pittman – Memorial University of Newfoundland

Abstract: The Watchmans Walk Problem attempts to find a minimum closed dominating walk (MCDW) in a connected graph. This walk can be thought of as an optimal route through which a single watchman can see every vertex in the graph. In this talk, we will consider the traditional WatchmansWalk problem on directed graphs. We explore the Watchmans Walk number for tournaments, and other directed graphs such as semicomplete digraphs, orientations of complete multipartite graphs, and DeBruijn graphs. We relate the length of a Watchmans Walk to the size of a minimum dominating set. We also consider the existence of tournaments with a Watchmans Walk of a specified length and multiplicity, and tournaments with a unique Watchmans Walk.

The Oriented Domination Polynomial

Iain Beaton – Dalhousie University

A dominating set of an oriented graph G is a subset of the vertices S such that each vertex in V-S has an in-neighbour in S. We introduce the oriented domination polynomial of G, denoted by D_o(G, x) is defined by D_o(G, x)= where is the number of oriented dominating of size i in G and is the size of the largest oriented dominating set. The oriented domination polynomial is a generalization of the domination polynomial for undirected graphs. We will discuss its computation, unimodality, and connection to the independence polynomial for forests and unicyclic graphs.

Chromatic Polynomials of Oriented Graphs

Danielle Cox - Mount Saint Vincent University

Abstract: The oriented chromatic polynomial of an oriented graph outputs the number of oriented k-colourings for any input k. In this talk we will fully classify those oriented graphs for which the oriented graph has the same chromatic polynomial as the underlying simple graph, closing an open problem posed by Sopena. The chromatic roots of the oriented chromatic polynomial will also be discussed. Joint with Chris Duffy of University of Saskatchewan.

Wednesday August 13^th, 2019

Chip Firing and Carbon Dioxide Sequestration

David Pike – Memorial University of Newfoundland

Abstract: We discuss a model of carbon dioxide sequestration that is based on chip firing on a graph. This is joint work with Thomas McCourt, Fendge Zhou, Valeria Bianchi and Diane Donovan.

Chip-Firing and Polyominoes

Todd Mullen – Dalhousie University

Abstract: Parallel Diffusion, a variant of chip-firing, was introduced in 2016 by Duffy et al. We will look at this process on complete graphs and count the number of unique chip distributions that can occur by relating them to polyominoes. This is joint work with Richard Nowakowski (Dalhousie) and Danielle Cox (MSVU).

Source Sink Diffusion

Jesse Preston - Mount Saint Vincent University

Abstract: In this talk we will introduce Source-Sink Diffusion. Preliminary results will be presented, and the periodicity of the process will be discussed. It is known that Diffusion of all graphs have period 1 or 2. We will show that with the addition of source and sink that this is not always the case. Joint work with D. Cox, T Mullen, and E. Wright.

Diffusion with Multiple Sources and Sinks

Emily Wright - Mount Saint Vincent University

Abstract: Consider the game of Diffusion, where at each time step, all vertices simultaneously send one chip to each neighbour with fewer chips. We introduce a variation of Diffusion, Source Sink Diffusion, that plays out as normal, but during each time step, a chip is given to the vertex adjacent to the source, and a chip is taken from the vertex adjacent to the sink. General characteristics of graphs with one source and sink in period 1 are discussed, and results on periodicity of graphs with multiple sources and sinks will be presented and compared to the results of Diffusion. Joint work with D. Cox, J. Preston, and T. Mullen.

On the Structure of 4-Regular Planar Well-Covered Graphs

Art Finbow – Saint Mary’s University

Abstract: A graph G is said to be well-covered if every maximal independent set of vertices has the same cardinality. In this paper we focus on the study of well-covered graphs which are 4-regular and planar. Joint work with Bert Hartnell, Saint Mary's University and Michael D. Plummer, Vanderbilt University

Multiple Qubit State Transfer on Paths

Christopher van Bommel – University of Waterloo

Abstract: Quantum computing would provide many advantages over traditional computing. One of the challenges in implementation is the transmission of information from one part of the computer to another. We model this transmission by continuous time quantum walks on graphs, which are quantum analogues of classical random walks, and consider conditions required to allow states to transfer with high fidelity. We briefly discuss characterizations for transferring single qubit states on paths with arbitrarily high fidelity under two different quantum walk models, and then discuss extending the techniques involved to analyze the transfer of multiple qubit states.

Path partitions and zero forcing on graphs

Zhiyuan (Owen) Zhang – Dalhousie University

Abstract: In the zero forcing process, an initial set of vertices is marked, and at each step, a marked vertex with exactly one unmarked neighbour marks this neighbour. The zero forcing number of a graph is the minimal size of the initial set, so that all vertices are marked at the end of the process. We give a characterization of graphs with a specific zero forcing number in terms of a path partition with special properties. We use this characterization to give new short proofs of several bounds on the zero forcing number. We also study graphs for which the zero forcing number equals the minimum degree.

The Threshold Dimension of a Graph

Lucas Mol – University of Winnipeg

Abstract: Let G be a graph. A set of vertices S of G is called a 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 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 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 irreducible graphs — those for which the threshold dimension is equal to the metric dimension. This is joint work with Matthew Murphy and Ortrud Oellermann.