CanaDAM 2013 Université Memorial de Terre-Neuve, 10 - 13 juin 2013 www.smc.math.ca//2013f

Graph Theory III
[PDF]

DANIELLE COX, Dalhousie University
All Terminal Reliability and Optimality  [PDF]

Let $G$ be a graph on $n$ vertices and $m$ edges. The all terminal reliability of $G$, Rel$(G,p)$, is the probability that at least a spanning tree is operational, given vertices always operate and edges operate independently with $p\in[0,1]$. In this talk we extend the values of $n$ and $m$ for which most optimal simple graphs do not exist, and settling an outstanding conjecture, prove that even if multiedges are allowed, there are still cases where most optimal graphs do not exist. (This is joint work with Jason Brown.)

KRYSTAL GUO, Simon Fraser University
Simple eigenvalues of vertex-transitive graphs and digraphs  [PDF]

A simple eigenvalue of a graph is an eigenvalue of the adjacency matrix with multiplicity 1. For graphs, there is a general pattern that having many simple eigenvalues tends to coincide with having small automorphism groups. The only vertex-transitive graph with all simple eigenvalues is $K_2$. In the case of digraphs, however, there are non-trivial vertex-transitive examples with all simple eigenvalues and we investigate such digraphs. In particular, a digraph with all simple eigenvalues is a DRR with an Abelian automorphism group. We will also look at properties of vertex-transitive graphs with many simple eigenvalues.

SADEGHEH HAGHSHENAS, Memorial University of Newfoundland
Spectrum of Packing and Covering of the Complete Graph with Stars  [PDF] [SLIDES]

The packing and covering numbers for the stars on up to six vertices were determined by Roditty in 1986. In this talk, for every possible leave graph (excess graph) we find the corresponding maximum packing (minimum covering) of the complete graph with stars on up to six vertices.

TERRY MCKEE, Wright State University, Dayton Ohio, USA
Requiring Pairwise Nonadjacent Chords in Cycles  [PDF] [SLIDES]

Let ${\cal G}_k$ be the class of graphs for which every cycle of length $k$ or more has at least $k-3$ pairwise nonadjacent chords. This makes ${\cal G}_4$ the class of chordal graphs and ${\cal G}_5$ the class of distance-hereditary graphs. I characterize ${\cal G}_k$ for all $k$ (they are disparate through $k=7$ and very simple beyond that). Motivated by ${\cal G}_4\cap{\cal G}_5$ being the class of ptolemaic graphs, I also characterize ${\cal G}_4\cap{\cal G}_5\cap{\cal G}_6$ (and beyond).

LUCAS MOL, Dalhousie University
On the uniformity dimension of hypergraphs  [PDF]

For a hypergraph $H=(V,E)$ and a field $\mathbb{F}$, a weighting of $H$ is a map $f:V\rightarrow \mathbb{F}$. A weighting is called \textit{stable} if the sum of the weights on each edge of $H$ is constant. The set of all stable weightings of $H$ forms a vector space over $\mathbb{F}$ called the \textit{uniformity space} of $H$ over $\mathbb{F}$, and its dimension is called the \textit{uniformity dimension} of $H$ over $\mathbb{F}$. For $l\geq 2$ the uniformity dimension of random $l$-uniform hypergraphs is shown to be almost surely 1. The uniformity dimensions of some highly structured hypergraphs are determined.