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…

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…

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…

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…

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…

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…

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,…