Réunion d'été SMC 2015
Université du Prince Edward Island, 5 - 8 juin 2015
Graphes, designs et hypergraphes
Org: Robert Bailey (Grenfell Campus, Memorial), Andrea Burgess (UNB Saint John) et Margaret-Ellen Messinger (Mount Allison)
[PDF]
Org: Robert Bailey (Grenfell Campus, Memorial), Andrea Burgess (UNB Saint John) et Margaret-Ellen Messinger (Mount Allison)
[PDF]
- ROBERT BAILEY, Grenfell Campus, Memorial University
Metric dimension of distance-regular graphs: a triennial update [PDF]
-
A resolving set for a graph $G$ is a collection of vertices chosen so that any vertex of $G$ is uniquely identified by the list of distances to the chosen few. The metric dimension of $G$ is the smallest size of a resolving set for $G$.
At the 2009 and 2012 CMS Summer Meetings, I gave talks on the metric dimension of distance-regular graphs. Now is the time for an update on this, focusing primarily on the case of imprimitive distance-regular graphs.
- ANTHONY BONATO, Ryerson University
A probabilistic version of the Game of Zombies and Survivors on graphs [PDF]
-
We consider a new probabilistic graph searching game played on graphs, inspired
by the familiar game of Cops and Robbers. In Zombies and Survivors, a set of
zombies attempts to eat a lone survivor loose on a given graph. The zombies randomly
choose their initial location, and during the course of the game, move directly toward the
survivor. At each round, they move to the neighbouring vertex that minimizes the distance
to the survivor; if there is more than one such vertex, then they choose one uniformly at
random. The survivor attempts to escape from the zombies by moving to a neighbouring
vertex or staying on his current vertex. The zombies win if eventually one of them eats the
survivor by landing on their vertex; otherwise, the survivor wins. The zombie number of
a graph is the minimum number of zombies needed to play such that the probability that
they win is strictly greater than 1/2. We present asymptotic results for the zombie numbers
of several graph families, such as cycles, hypercubes, incidence graphs of projective planes,
and Cartesian and toroidal grids.
- NANCY CLARKE, Acadia University
2-Limited Packings of Cartesian Products [PDF]
-
For a fixed integer $k$, a set of vertices $B$ of a graph $G$ is a \textit{$k$-limited packing} of $G$ provided that the closed neighourhood of any vertex in G contains at most $k$ elements of $B$. The size of a largest possible $k$-limited packing in $G$ is denoted $L_k(G)$ and is the $k$-limited packing number of $G$.
In this talk, we investigate the 2-limited packing number of Cartesian products of paths.
We show that the function $\Delta [L_2(P_m \square P_n)] = L_2(P_m \square P_n) -L_2(P_m \square P_{n-1})$ is eventually periodic, and thereby give closed formulas for $L_2(P_m \square P_n)$, $m = 1, 2, \ldots, 5$.
The techniques we use are suitable for establishing other types of packing and domination
numbers for Cartesian products of paths and, more generally, for graphs of the form $H \square P_n$.
This is joint work with Robert P. Gallant.
- ROBERT CRAIGEN, University of Manitoba
The group of odd-weight Boolean complementary pairs [PDF]
-
{\bf Ternary complementary pairs} are pairs of ternary (i.e., having elements $0,1,-1$) sequences with zero total autocorrelation. Unlocking the mysteries of for which parameters these exist and what their internal structure comprises has proven a tough problem. Many years ago we conceived a divide-and-conquer strategy for such questions in which the first stage was to solve the "boolean" version of the problem by reducing modulo 2, which gives {\bf Boolean complementary pairs}, focussing exclusively on identifying all the possible configurations of zeros. From a highly sporadic class of objects arose complete and simple order, in one case (even weight) and remarkably regular but still complex in the other (odd weight). The members of this class are associated with the elements of an infinite group. This talk is about the solution of the a word problem on that group to yield a straightforward procedure for generating these pairs in sequence with no searching or similarly bulky computational overhead.
- PETER DANZIGER, Ryerson University
On the Hamilton-Waterloo Problem with odd orders [PDF]
-
Given non-negative integers $v, m, n, \alpha, \beta$, the Hamilton-Waterloo problem asks for a factorization of the complete graph $K_v$ into $\alpha$ $C_m$-factors and $\beta$ $C_n$-factors. We may assume without loss of generality that $n\geq m$. Clearly, $n,m\geq 3$ odd, $m\mid v$, $n\mid v$ and $\alpha+\beta = (v-1)/2$ are necessary conditions.
In this talk we present results that show that these necessary conditions are sufficient when $v$ is a multiple of $nm$, except possibly when $\beta=1$ or 3, or $v=mn$ and $\alpha < \frac{n-1}{2}$.
This is joint work with Andrea Burgess and Tommaso Traetta. I will discuss some of the history of the problem and present the main result, Tommaso Traetta will be presenting some further results on which this one rests in his talk.
- PETER DUKES, University of Victoria
Designs covered by small subdesigns [PDF]
-
Given a pairwise balanced design and some subset $S$ of its points, the flat (subdesign) generated by $S$ is the intersection of all flats containing $S$. It is natural to say that the dimension of a design is the maximum integer $d$ such that the flat generated by any $d$ points is proper. For instance, affine space AG$_d(q)$ has dimension $d$ under this definition because all $d$-point-generated flats have size at most $q^{d-1}$, but some set of $d+1$ points generate the whole space.
Our main result is that, for any $K$ and $d$, there exist, for all sufficiently large admissible $v$, a pairwise balanced design PBD$(v,K)$ such that all $d$-point-generated flats are bounded by a constant independent of $v$. This gives an existence theory for designs of dimension at least $d$ (in a rather strong sense).
For the case $K = \{3,4,5\}$ and $d=3$, it is possible to construct designs of each possible size with a universal upper bound of $94$ on all generated flats. This is of independent interest for a certain extremal problem on edge-colourings. An easy transformation from this case also leads to latin squares covered by small subsquares.
- DANNY DYER, Memorial University of Newfoundland
Achieving excesses and leaves: packings and coverings of complete graphs with small trees [PDF]
-
A well known result in combinatorial designs characterizes the leaves and excesses of maximum packings and minimum coverings of the complete graph with triangles in those cases where a decomposition is not possible. Similar work was done by Roditty in the 1980s for trees with few edges. However, unlike the triangle case, with trees, the leaves (excesses) may vary greatly. For trees with at most 5 edges, we achieve all leaves and excesses of maximum packings and minimum coverings. Joint work with Sadegheh Haghshenas and Nabil Shalaby.
- STEPHEN FINBOW, St Francis Xavier
Hamiltonicity of Bell and Stirling Colour Graphs [PDF]
-
For a given graph $G$ the $k$- Colour Graph has been defined as the graph of colourings of $G$ using $k$ or fewer colours, where two colourings $c_1$ and $c_2$ are adjacent if they agree on all but one vertex of $G$. That is there is a vertex $v\in V(G)$ such that $c_1(x)=c_2(x)$ for all $x\in V(G)/\{v\}$.
Each colouring of $G$ induces an equivalence relation of the vertices. Specifically, for a colouring $c$, $x$ is related to $y$ if $c(x)=c(y)$. Since this is the way colourings are normally viewed, a more intuitive approach would perhaps be consider only the partitions induced by each of the colourings of $G$. That is define the $k$-Bell Colour Graph, $\mathcal{B}_k(G)$ from $k$-Colour Graph of $G$ by identifying colourings $c_1$ and $c_2$ if $[x]_{c_1}=[x]_{c_2}$ for every $x\in V(G)$. The $k$-Stirling Colour Graph $\mathcal{S}_k(G)$, which is the subgraph of $\mathcal{B}_k(G)$ induced by the vertices in $V(\mathcal{B}_k(G))-V(\mathcal{B}_{k-1}(G))$. This graph, $\mathcal{S}_k(G)$, is the graph of partitions of $G$ induced by colourings using exactly $k$ colours. We will discuss some results on the Hamiltonicity of $k$-Bell Colour Graphs and $k$-Stirling Colour graphs.
This is joint work with G. MacGillivray.
- SHANNON FITZPATRICK, University of Prince Edward Island
Cops and Robber on Circulant Graphs [PDF]
-
From a result of Frankl (1987) on the copnumber of Cayley graphs, it is know that the copnumber of any 4-regular Circulant graph is at most 3. In this talk, characterizations of 4-regular circulant graphs of copnumber 1, 2, and 3, respectively, will be given. Through the use of wreath products, the copnumbers of additional classes of circulant graphs can then be determined. Finally, as a consequence of expressing Circulant graphs in terms of wreath products, a characterization of tandem-win circulant graphs is found.
- GENA HAHN, Universite de Montreal
On cycle double covers for infinite graphs [PDF]
-
We look at the cycle double cover conjecture for infinite graphs, prove it for some special cases and generalise it, proving the generalised version for trees. In the process we mentioned some related problems and their partial solutions.
- JARED HOWELL, Memorial University - Grenfell Campus
The Watchman's Walk on Block Intersection Graphs of Steiner Triple Systems [PDF]
-
A watchman's walk, in a graph $G$, is a minimum closed dominating walk of $G$. The block intersection graph of a Steiner triple system, $S$, has vertices labelled by the blocks of $S$ and an edge between two vertices if and only if corresponding blocks have a point in common. The structure of these block intersection graphs allows us to find bounds on the watchman's walk for such graphs and give constructions to achieve these bounds.
- EDUARDO MARTINEZ-PEDROZA, Memorial University
Coarse Geometry of the Firefighter Problem [PDF]
-
A fire breaks out on a finite set of vertices of a graph $G$. Then a firefighter protects $n$ vertices not on fire. At each subsequent integral time, the fire spreads to all adjacent unprotected vertices and then the firefighter protects $n$ unburned vertices. The graph $G$ has the $n$-containment property if for every finite initial fire, there is an strategy to contain the fire protecting $n$ vertices at each turn. A graph $G$ has the fire containment property if there is an integer $n$ such that it has the $n$-containment property. \newline
Quasi-isometry is an equivalence relation on metric spaces which favors the large scale geometry and ignores the small scale details. Our main result is that for the class of graphs with a bound on their degree, having the fire containment property is preserved by quasi-isometry. Some sample consequences of our result are that any regular tiling of the Euclidean plane has the fire containment property, no regular tiling of the $n$-dimensional Euclidean space has the containment property if $n>2$, no regular tiling of the n-dimensional hyperbolic space has the containment property if $n\geq 2$. \newline
This is joint work with Danny Dyer and Brandon Thorne from Memorial University.
- LUCAS MOL, Dalhousie University
Shape and roots of the node reliability polynomial [PDF]
-
Consider a network $G$ in which each node operates independently with probability $p\in(0,1).$ The \textit{node reliability polynomial} of $G$ is the probability that the operational nodes can all communicate in the induced subgraph that they generate. We investigate the shape and roots of the node reliability polynomial, and compare our findings to those for all-terminal reliability. While the all-terminal reliability polynomial of any connected graph is increasing on $(0,1),$ we prove that the node reliability polynomial of any sparse graph of sufficiently large order has an interval of decrease. We present several families of graphs with real, positive node reliability roots that tend to infinity. This differs greatly from the situation for all-terminal reliability polynomials, where it is conjectured that all roots are bounded. This is joint work with Jason Brown.
- KERRY OJAKIAN, BCC of CUNY
Capture time of cop-win graphs [PDF]
-
The game of cops and robber is a two player game, played on a graph, between a cop and a robber. First the cop chooses a vertex, then the robber chooses a vertex; then play alternates. On a turn, a player may move to an adjacent vertex or remain still. A graph is cop-win if the cop can guarantee a win. The capture time of a cop-win graph is the number of cop moves required to win. Let capt(n) be the capture time of a graph on n vertices with maximum capture time. Gavenciak showed that capt(n) = $n-4$, for $n \ge 7$, and characterized these extremal graphs. We show how to use a new tool of "corner ranking" to prove these results more efficiently. This is joint work with David Offner.
- DAVID PIKE, Memorial University of Newfoundland
Equitably Coloured BIBDs [PDF]
-
A balanced incomplete block design (BIBD) with parameters $v$, $k$ and $\lambda$ consists of a $v$-set $V$ of points together with a set $\cal{B}$ of $k$-subsets of $V$ called blocks, such that each 2-subset of $V$ is a subset of exactly $\lambda$ blocks of $\cal{B}$. A colouring of a design $(V,\cal{B})$ is a function $f : V \rightarrow C$, where $C=\{c_1,\ldots,c_\ell\}$ is a set of elements called colours. A weak colouring of a design is a colouring $f$ such that $|\{ f(x) : x \in B \}| > 1$ for each $B \in \cal{B}$ (i.e., each block has at least two colours). An equitable colouring is a colouring such that for each block $B \in \cal{B}$ the number of points of any colour $c_i \in C$ is within 1 of the number of points of any other colour $c_j \in C$ (i.e., $-1 \leq |B \cap C_i| - |B \cap C_j| \leq 1$, where $C_t = \{ x \in V : f(x)=c_t\}$ denotes those points of $V$ having colour $c_t$). We determine necessary and sufficient conditions for equitably colourable BIBDs. This is joint work with Robert Luther.
- ELHAM ROSHANBIN, Dalhousie University
Graph Burning [PDF]
-
The spread of social contagion is an active area in social network analysis. Assume that we want to spread a message among all the users of a network. Knowing the structure of the network, we may ask how fast can we do this and what is the best strategy? Burning number is a new graph parameter which measures the speed of contagion in the underlying graph of a social network. In this talk we introduce this parameter and we explore some results that we have found on the burning number.
This is joint work with my supervisors Anthony Bonato and Jeannette Janssen.
- MATEJA SAJNA, University of Ottawa
Eulerian properties of 3-uniform hypergraphs [PDF]
-
A flag of a hypergraph $H=(V,E)$ is an ordered pair $(v,e)$ with $v \in V$, $e \in E$, and $v \in e$. A closed trail of $H$ is a sequence $W=v_0e_0v_1e_1v_2\ldots v_{k-1}e_{k-1}v_0$ with $v_i \in V$, $e_i \in E$, and $v_i,v_{i+1} \in e_i$ for each $i \in \mathbb{Z}_k$ such that no flag --- that is, $(v_i,e_i)$ or $(v_{i+1},e_i)$ --- is repeated. A closed trail $W$ is called an Euler tour of $H$ if it traverses each flag $(v,e)$ of $H$ exactly once, and a strict Euler tour if it traverses each edge of $H$ exactly once. A family of closed trails of $H$ that jointly traverse each edge of $H$ exactly once is called an Euler family.
For a connected graph, the concepts of Euler tour, strict Euler tour, and Euler family are identical, however, for a general hypergraph, they give rise to three rather distinct problems. For example, while the problems of existence of an Euler tour and Euler family are polynomial on the set of all hypergraphs, the problem of existence of a strict Euler tour is NP-complete even just on the set of all linear 2-regular 3-uniform hypegraphs. In this talk, we shall briefly compare the three problems, and then focus on two main results: (1) every 3-uniform hypergraph without cut edges has an Euler family, and (2) every triple system has a strict Euler tour.
Joint work with Amin Bahmanian and Andrew Wagner.
- ASIYEH SANAEI, Acadia University
Generalized Dutch Windmills Skolem Labelling [PDF]
-
Let $D_{m,n}$ be a graph on $2k$ vertices and composed of two cycles $C_m$ and $C_n$, $n\ge m$, with a vertex in common. We answer the question of whether it is possible to assign the labels $1,1,2,2,3,3,\dots, k,k$ to the vertices of $D_{m,n}$ such that the two vertices labelled $i$ are of distance $i$ for each $1\le i\le k$; such a labelling is called Skolem labelling and may be used in testing distance reliability of networks. We show that $D_{m,n}$ does not have a Skolem labelling if and only if $n-m\equiv 3,5$ (mod 8) and $m$ is odd, thereby introducing a new way for proving that a Skolem labelling does not exist.
- ALYSSA SANKEY, University of New Brunswick
On association schemes constructed from $t$-fold covers of schemes [PDF]
-
Let ${\cal A}$ be an association scheme with vertex set $X$ and relations $\{R_i\}$, and $\omega$ a weight function on the edges of the complete graph on $X$. If $\omega$ takes values in the group of $t^\text{th}$ roots of unity, we may view the weight as a $t$-fold cover of $K_n$. We assume that $\omega$ has certain regularity properties depending on ${\cal A}$. In this talk, we describe the construction of an association scheme on $tn$ vertices, whose structure constants are analogous to those of ${\cal A}$ in that they count a subset of the triples $(x,y,z)$ of vertices of fixed adjacency type -- that is, $(x,y)\in R_i$, $(y,z)\in R_j$ and $(x,z)\in R_k$ -- the subset consisting of those with a fixed weight $\alpha=\omega(x,y)\overline{\omega(x,z)}\omega(y,z)$. We conclude with explicit examples, noting in particular some non-symmetric schemes that arise from 4-fold covers of strongly regular graphs.
- TOMMASO TRAETTA, Ryerson University
On the Hamilton-Waterloo problem for a class of Cayley graphs [PDF]
-
The Hamilton-Waterloo problem $HWP(\Gamma; m,n; \alpha$, $\beta)$
asks for a factorization of the simple graph $\Gamma$ into
$\alpha$ $C_m$-factors and
$\beta$ $C_n$-factors. The classic version of the problem, that is, the case in
which $\Gamma$ is the complete graph is still open,
although it has been the subject of
an extensive research activity.
In this talk, I will consider the Cayley graph $C_m[n]=Cay(\mathbb{Z}_{m}\times \mathbb{Z}_{n}, S)$ with connection set $S=\{1,-1\}\times \mathbb{Z}_{n}$ and present an almost complete solution to $HWP(C_m[n]; m,n; \alpha,\beta)$ with $m$ and $n$ odd. Peter Danziger will show how this result can be used to make progress on the classic problem.
This is joint work with Andrea Burgess and Peter Danziger.
