Atlantic Graph Theory Seminars

The Atlantic Graph Theory Seminars series will take place every Wednesday from 3:30-4:30 ADT online via zoom.

They are sponsored by AARMS: Atlantic Association for Research in the Mathematical Sciences.

The talks, provided by researchers, postdocs and graduate students, will be on a variety of current topics in graph theory.

If you would like to give a talk or to be added to our mailing list please email one of the organizers.

Organizers:
Jason Brown (Dalhousie University: jason.brown@dal.ca )
Danielle Cox (Mount St. Vincent University: danielle.cox@msvu.ca)

UPCOMING TALKS:

PAST TALKS:

Date: Oct 14
Speaker: Dr. David Pike, Memorial University of Newfoundland
Title: Perfect 1-Factorisations
Abstract: A matching in a graph G s a subset $M \subseteq E(G)$ of the edge set of $G$ such that no two edges of $M$ share a vertex. A 1-factor of a graph $G$ is a matching $F$ in which every vertex of $G$ is in one of the edges of $F$. If $G$ is a $\Delta$-regular graph of even order then we can ask whether $G$ admits a 1-factorisation, namely a partition of its edge set into $\Delta$ 1-factors. Suppose that $F_1, F_2, \ldots, F_\Delta$ are the 1-factors of a 1-factorisation $\cal F$ of a $\Delta$-regular graph $G$. If, for each $1 \leq i < j \leq \Delta$, the union $F_i \cup F_j$ yields a Hamilton cycle in $G$, then we say that $\cal F$ is a perfect 1-factorisation. We will discuss some of the history and properties of 1-factorisations, including the recent discovery of a perfect 1-factorisation of $K_{56}$.
Click here for Dr Pike's Talk Slides
Click here for Dr Pike's Talk Video

Date: Oct 21
Speaker: Dr. Ben Cameron, University of Guelph
Title: Families of graphs containing only finitely many vertex-critical graphs.
Abstract: In this talk, motivated by algorithmic aspects of graph colouring, we will consider the problem of classifying vertex-critical graphs in families of graphs. We will complete a dichotomy theorem for the number of k-vertex-critical H-free graphs when H is a graph of order four. Our results also reduce the remaining open problem for graphs of all orders to two families of graphs. Toward implementing the corresponding graph colouring algorithms, we then improve upon previous research to show tight upper bounds on the order and independence number of k-vertex-critical graphs in another family of graphs, allowing for exhaustive generation of these graphs for k at most 7 . Joint work with Chính Hoàng and Joe Sawada.
Click here for Dr Cameron's Talk Slides
Click here for Dr Cameron's Talk Video

Date: Oct 28
Speaker: Iain Beaton, PhD Candidate, Dalhousie University
Title: The Average Order of Dominating Sets of a Graph
Abstract: 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 1/2 for almost all graphs.
Click here for Iain Beaton's Talk Slides
Click here for Iain Beaton's Talk Video

Date: Nov 4
Speaker: Dr Andrea Burgess, University of New Brunswick, Saint John
Title: Equitably colourable cycle decompositions
Abstract: A $c$-colouring of a decomposition of a graph $G$ is an assignment of $c$ colours to the vertices of $G$. A colouring is equitable if each colour is represented (as closely as possible) an equal number of times on each block, i.e. for any two colours $i$ and $j$, the number of vertices of colour $i$ and $j$ in any given block differ by at most 1. In this talk, we give an overview of colourings of designs and cycle decompositions, and present some recent joint results with Francesca Merola on the existence of equitably 2-colourable cycle decompositions of the cocktail party graph. In particular, we give a complete existence result for equitably 2-colourable $k$-cycle decompositions of $K_v-I$ in various cases, including that $v \equiv 0$ or $2$ (mod $k$); $k$ is a power of 2; $k \in \{2q,4q\}$ for $q$ a prime power; or $k \leq 30$.
Click here for Andrea Burgess' Talk Slides
Click here for Andrea Burgess' Talk Video

Date: Nov 18
Speaker: Kyle MacKeigan, PhD Candidate, Dalhousie University
Title: Orthogonal Colourings of Graphs
Abstract: Two colourings of a graph are orthogonal if they have the property that when two vertices receive the same colour in one colouring, then those vertices receive distinct colours in the other colouring. In this talk, the importance of perfect orthogonal colourings is demonstrated. Then, perfect orthogonal colourings of Cayley graphs and tree graphs are constructed. To conclude, it is shown how the Cartesian, tensor, and strong graph product can be used to generate perfect orthogonal colourings.
Click here for Kyle MacKeigan's Talk Slides
Click here for Kyle MacKeigan's Talk Video

Date: Nov 25
Speaker: Dr Jared Howell, Memorial University of Newfoundland, Grenfell Campus
Title: Gracefully labelling windmills using Skolem-like sequences
Abstract: To gracefully label a graph G, assign each vertex v ∊ V(G) a distinct label l(v) from {0,1,2,...,|E(G)|}, such that {|l(u)-l(v)| : uv ∊ E(G)}={1,2,3,...,|E(G)|}. In this talk we will examine constructive techniques using Skolem-like sequences to gracefully label windmills of cycles. This includes new constructive techniques for known results as well as new results on windmills with vanes of mixed cycle length.
Click here for Jared Howell's Talk Slides
Click here for Jared Howell's Talk Video

Date: Dec 2
Speaker: Dr Melissa Huggan, Ryerson University
Title: The Cheating Robot and Insider Information
Abstract: Throughout this talk, we explore a deterministic model as an alternative approach to studying simultaneous play combinatorial games. We call this the Cheating Robot model. This model forces both players to move at the same time, but one player has extra information about where their opponent is going to move and can react accordingly. We discuss some general theory and explore a case study to get some insight into this model. This is joint work with Richard J. Nowakowski.
Click here for Dr Huggan's Talk Slides

Date: Dec 9
Speaker: Dr Erin Meger, Université du Québec à Montréal
Title: The Iterated Local Model for Social Networks

Abstract:

Complex networks are said to exhibit four key properties: large scale, evolving over time, small world properties, and power law degree distribution. The Preferential Attachment Model (Barab´asi–Albert, 1999) and the ACL Preferential Attachment Model (Aiello, Chung, Lu, 2001) for random networks, evolve over time and rely on the structure of the graph at the previous time step. Further models of complex networks include: the Iterated Local Transitivity Model (Bonato, Hadi, Horn, Pralat, Wang, 2011) and the Iterated Local Anti-Transitivity Model (Bonato, Infeld, Pokhrel, Pralat, 2017). In this talk, we will define and discuss the Iterated Local Model. This is a generalization of the ILT and ILAT models, where at each time step edges are added deterministically according to the structure of the graph at the previous time step.
Click here for Dr Meger's Talk Slides

Date: Jan 13:
Speaker: Dr Stephen Finbow, Saint Francis Xavier University

Title: The γ-graph of a graph

Abstract: For a graph G = (V, E), the γ-graph of G, G(γ) = (V (γ), E(γ)), is the reconfiguration graph whose vertex set is the collection of minimum dominating sets, or γ-sets of G, and two γ-sets are adjacent in G(γ) if they differ by a single vertex and the two different vertices are adjacent in G. The γ-graph of G was introduced by Fricke et al. in 2011 where they studied properties of γ-graphs, and raised seven questions. In this seminar we will discuss the study of γ-graphs to date with a focus on the progress of these questions.
Click here for Dr Finbow's Talk Slides
Click Here for Dr Finbow's Talk Video

Date: Jan 20:
Speaker: Dr Hugh Thomas, Université du Québec à Montréal

Title: Dynamical algebraic combinatorics and independence sets of graphs
Abstract: Dynamical algebraic combinatorics is a relatively new (and fun!) topic, which looks at cyclic group actions on objects from algebraic combinatorics, inspired by some questions coming from dynamical systems. I will give an introduction to the area, focusing on an action I have defined with Nathan Williams on the independent sets of a graph (arXiv:1805.00815). We also construct a partial order on the set of independent sets of a graph, which may be of independent interest.

Click here for Dr Thomas' Talk Slides
Click here for Dr Thomas' Talk Video

Date: Jan 27:
Speaker: Jordan Barrett, PhD Candidate, McGill University
Title: Counting loops and multi-edges in the superposition of a fixed graph and a random graph
Abstract: We are given a fixed graph and we attach half-edges to each vertex. We then pair the half-edges as per the configuration model to create a partially random graph which could have multi-edges even if the underlying random graph does not. We will show that, under the appropriate conditions, the probability that such a graph is simple asymptotically approaches a constant. This is joint work with Dr. Louigi Addario-Berry and the argument is an extension of an argument given by Dr. Remco van der Hofstad in his book “Random Graphs and Complex Networks”.

Click here for Jordan Barrett's Talk Slides
Click here for Jordan Barrett's Talk Video

Date: Feb 10:

Speaker: Dr Anthony Bonato, Ryerson University
Title: The localization game played on graph
Abstract: Graph searching investigates combinatorial models for the detection or neutralization of an adversary’s activity on a network. One such model is the \emph{localization game}, where pursuers use distance probes to capture an invisible evader. We present new results on the \emph{localization number} of a graph, which is the minimum number of pursuers needed to capture the evader. We survey what is known and unknown for the localization number, discuss connections with the chromatic number, and give bounds on graph families such as hypercubes, incidence graphs of combinatorial designs, and Kneser graphs.
Click here for Dr Bonato's Talk Slides
Click here for Dr Bonato's Talk Video

Date: Feb 24:

Speaker: Dr Gary Gordon, Lafayette College
Title: Permutations of finite subsets of R² generated by Euclidean distances
Abstract:
Given a finite set of points S = {P1, P2, . . . , Pn} and a vantage point V, generate an ordering of the points of S by measuring the Euclidean distance from V to each of the points of S, ordering them from nearest to farthest. As the vantage point moves around the plane, different orderings will be generated. We are interested in the maximum, minimum, and intermediate values achievable for different point-sets S. (Good and Tideman solved the maximum problem in all dimensions in the 1970s.) We also consider a generalization that uses two vantage points, using the average distance (d(V1, Pk) + d(V2, Pk))/2 to the points of S to generate an ordering.
Click here for Dr Gordon's Talk Slides
Click here for Dr Gordon's Talk Video

Date: Mar 3:

Speaker: Dr Jeannette Janssen, Dalhousie University
Title: An approximation algorithm for finding the zero-forcing number of a graph

Abstract: Consider the following graph process: Given a graph with vertices coloured black or white. At each step, if a black vertex has exactly one white neighbour, then this neighbour turns black. If the process turns all vertices black, then the initial set of black vertices is azero-forcing set. The minimum size of a zero-forcing set in a graph G is called the zero-forcing number and denoted by z(G). The study (and name) of the zero-forcing process is motivated by a problem from combinatorial matrix theory.

We will show that a z(G)=k if and only if G can be partitioned into k paths with certain properties. This characterization leads to short proofs of several known results. We then use this characterization to give an algorithm that finds a zero-forcing set of size at most (tw-1)z(G), where tw is the tree-width of G. This is joint work with Ben Cameron, Rogers Mathew, and Zhiyuan (Owen) Zhang.
Click here for Dr Janssen's Talk Slides
Click here for Dr Janssen's Talk Video

Date: Mar 10 :

Speaker: Dr Nancy Clarke, Acadia University
Title: Cops and

Robber: When the Cops Need Glasses

Abstract: Cops and Robber is a well-studied pursuit-evasion game played on graphs. In this talk, I’ll discuss several variations of the game in which the cops' ability to see the robber is impaired. In the farsighted (hyperopic) version of the game, the robber is invisible to the cop side unless outside the neighbourhood of a cop. We present a variety of results, including a characterization of the graphs on which a single cop suffices to guarantee a win, and we also consider graphs in terms of diameter and planarity. In the nearsighted (limited visibility) version of the game, the cops can only see the robber when the distance between them is at most a fixed parameter l. We will see that the cops' strategy consists of a phase in which they need to see the robber (i.e. move within distance l of the robber), followed by a phase in which they capture the robber. For some graphs, it is the first phase which is the most expensive in terms of cops while, for others, it is the second. Our results include a characterization of those trees on which k cops are sufficient to guarantee a

win for all l > 1. Work on the first version is joint with A. Bonato, D. Cox, S. Finbow, F. Mc Inerney, and M. Messenger, and on the second with D. Cox, C. Duffy, D. Dyer, S. Fitzpatrick, and M. Messinger.

Date: Mar 17:

Speaker: Dr Peter Danziger, Ryerson University

Title: The Oberwolfach a​nd Hamilton-Waterloo problems
Abstract:

Given a graph $G$, a 2-factor is a spanning subgraph of $G$ where every vertex has degree 2, and is hence a collection of cycles. A 2-factorization of $G$ is a set of 2-factors that between them partition the edges of $G$. Given a graph $G$ and a 2-factor $F$, the Oberwolfach problem asks for a 2-factorization of $G$ into factors isomorphic to $F$. Given a graph $G$, two 2-factors $F_1$ and $F_2$ and non-negative integers $\alpha$ and $\beta$, the Hamilton-Waterloo problem asks for a 2-factorization of $G$ into $\alpha$ factors isomorphic to $F_1$ and $\beta$ factors isomorphic to $F_2$. Classically, $G$ is the complete g​raph, $K_v$, or $K_v$ minus a 1-factor when $v$ is even. However, other options for $G$, such as a `blowup' of a complete graph or a cycle are also relevant in obtaining solutions to the original problem.
Click here for Dr Danziger's Talk Slides

Click here for Dr Danziger's Talk Video

Date: Mar 24:

Speaker: Dr Danielle Cox, Mount Saint Vincent University
Title: Chromatic Polynomial of 2-Edge-Coloured Graphs
Abstract: In this talk we extend the definition of chromatic polynomial to 2-edge-coloured graphs. We will provide results regarding the computation of the polynomial, location of roots and characterizing 2-edge-coloured graphs whose chromatic polynomial is equal to that of the underlying graph.This is joint work with Chris Duffy (University of Saskatchewan) and Iain Beaton (Dalhousie University).
Click here for Dr Cox's Talk Slides
Click here for Dr Cox's Talk Video

Date: Apr 7:

Speaker: MacKenzie Carr, Simon Fraser University
Title: Enumerating Digitally Convex Sets in Graphs

Abstract: Given a finite set V, a convexity, C, is a collection of subsets of V that contains both the empty set and

the set V and is closed under intersections. The elements of C are called convex sets. The digital convexity on the vertex set of a

graph, originally introduced as a tool for processing digital images, is defined as follows: a subset S of V(G) is digitally convex if,

for any vertex v in V(G), whenever N[v] is contained in N[S], then v is in S. Or, equivalently, S contains every vertex for which it is a local dominating set. Lafrance, Oellermann and Pressey (2015) found sharp upper and lower bounds on the number of digitally

convex sets in trees, as well as determining an exact formula for the number of digitally convex sets of several subclasses of trees, including paths. In this talk, we discuss the extension of some of these results to k-trees, as well as the use of cyclic binary strings and binary arrays to enumerate the digitally convex sets of cycles and of the Cartesian product of paths.
Click here for MacKenzie's Talk Slides
Click here for MacKenzie's Talk Video

Thank you to our sponsor, The Atlantic Association for Research in the Mathematical Sciences (AARMS)