# Past Events › Atlantic Graph Theory Seminar

## October 2020

### Atlantic Graph Theory Seminar: David Pike (Memorial)

Perfect 1-Factorisations A matching in a graph \$G\$ is 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…

Find out more »

### Atlantic Graph Theory Seminar: Dr. Ben Cameron (University of Guelph)

Title: Families of graphs containing only finitely many vertex-critical graphs. 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…

Find out more »

### Atlantic Graph Theory Seminar: Iain Beaton (PhD Candidate, Dalhousie University)

The Average Order of Dominating Sets of a Graph 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…

Find out more »

## November 2020

### Atlantic Graph Theory Seminar: Dr Andrea Burgess (University of New Brunswick, Saint John)

Equitably colourable cycle decompositions 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…

Find out more »

### Atlantic Graph Theory Seminar: Kyle MacKeigan (PhD Candidate, Dalhousie University)

Orthogonal Colourings of Graphs 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…

Find out more »

### Atlantic Graph Theory Seminar: Dr Jared Howell (Memorial University of Newfoundland, Grenfell Campus)

Gracefully labelling windmills using Skolem-like sequences 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. The Atlantic Graph Theory Seminar series will take place every Wednesday…

Find out more »

## December 2020

### Atlantic Graph Theory Seminar: Dr Melissa Huggan (Ryerson University)

The Cheating Robot and Insider Information 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…

Find out more »

### Atlantic Graph Theory Seminar: Dr Erin Meger (Université du Québec à Montréal)

The Iterated Local Model for Social Networks 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,…

Find out more »

## January 2021

### Atlantic Graph Theory Seminar: Dr Stephen Finbow, Saint Francis Xavier University

The γ-graph of a graph 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,…

Find out more »