2014 CMS Summer Meeting

University of Manitoba, June 6 - 9, 2014

Poster Abstract Submission Form Plenary, Prize and Public Lectures By session By speaker Posters

Graphs and Hypergraphs
Org: David Gunderson (Manitoba), Bill Kocay (Manitoba) and Ortrud Oellermann (Winnipeg)
[PDF]

ANTHONY BONATO, Ryerson University Independence densities of hypergraphs [PDF]

We consider the number of independent sets in hypergraphs, which allows us to define the independence density of countable hypergraphs. Hypergraph independence densities include a broad family of densities over graphs and relational structures, such as $F$-free densities of graphs for a given graph $F.$ We consider the rationality of independence densities of hypergraphs, and present extensions using independence polynomials.

RICHARD BREWSTER, Thompson Rivers University The complexity of signed graph homomorphisms [PDF]

Given a graph $G=(V,E)$, a \textit{signing} of $E$ is the assignment of $+$ or $-$ to each edge of $G$. Let $\Sigma \subseteq E$ be the set of negative. We call $(G,\Sigma)$ a \textit{signed graph}. To \textit{switch} at a vertex $v$ is a resigning of all the positive edges incident at $v$ to negative and vice versa. Two signed graphs $(G,\Sigma)$ and $(G,\Sigma')$ are equivalent if one can be obtained from the other by a sequence of switches. The class of all signed graphs equivalent to $(G,\Sigma)$ is denoted $[G, \Sigma]$.

A \textit{homomorphism} of $(G,\Sigma) \to (H,\Pi)$ is a vertex map that preserves edges and their signs. A homomorphism of equivalence classes $[G, \Sigma] \to [H, \Pi]$ exists if some member $(G, \Sigma') \in [G, \Sigma]$ admits a homomorphism to some member $(H, \Pi') \in [H, \Pi]$. In this talk we examine and contrast the computational complexity of determining the existence of signed graph homomorphisms in the case that switching is not allowed, i.e. viewing the objects as edge-coloured graphs, and where switching is allowed, i.e. homomorphisms of equivalence classes. In particular, we give a dichotomy theorem for the latter case.

JASON BROWN, Dalhousie University G-Convexity of Graphs [PDF]

A convexity or alignment on a finite set $V$ is a collection of subsets of $V$ containing the empty set, and the whole set $V$, and is closed under intersection; this forms a natural combinatorial generalization of convexity in euclidean space. Now let $G$ be a graph of order $n$. A subset $C$ of vertices of G is $g$-convex if for every pair $u,v\in C$ the vertices on every $u$--$v$ geodesic (i.e. shortest $u$--$v$ path) belong to $C$. The set of $g$-convex subsets of a graph are an interesting subfamily of alignments. In this talk we will discuss three aspects of $g$-convexity: the structure of $g$-minimal graphs (those that have the minimal number of g-convex sets), the complexity of counting $g$-convex sets in a graph, and when there exists $g$-convex sets of all cardinalities from $0$ to $n$. (This research is joint with O. Oellermann.)

STEPHEN FINBOW, St. Francis Xavier Vertex Colouring of Plane Graphs with Restrictions Given by Faces [PDF]

A cyclic colouring of a 2-connected plane graph (a planar embedding of a planar graph) was first introduced by Ore and Plummer and is a proper colouring where no two vertices on the same face receive the same colour. Czap and Jendrol' introduced the concept of parity vertex $k$-colouring on a plane graph (a proper colouring where a colour must appear 0 or an odd number of times on each face) as a strengthening of a proper colouring but a relaxation of the concept of cyclic colouring. We will discuss an extension of a will discuss a natural generalisation of a parity vertex $k$-colouring. This is joint work with Christopher van Bommel.

ANDREI GAGARIN, Royal Holloway, University of London The bondage number of graphs on topological surfaces and Teschner's conjecture [PDF]

The bondage number of a graph is the smallest number of its edges whose removal results in a graph having a larger domination number. The decision problem for the bondage number is known to be NP-hard. We provide constant upper bounds for the bondage number with respect to embeddability of graphs on topological surfaces. We improve upper bounds for the bondage number in terms of the maximum vertex degree and the orientable and non-orientable genera of graphs. Also, we present stronger upper bounds for graphs with no triangles and graphs with the number of vertices larger than a certain threshold in terms of graph genera. This settles Teschner's Conjecture in the affirmative for almost all graphs. As an auxiliary result, we show tight lower bounds for the number of vertices of graphs 2-cell embeddable on topological surfaces of a given genus.

Joint work with Vadim Zverovich, University of the West of England

SHONDA GOSSELIN, University of Winnipeg Metric Dimension of circulant graphs and Cayley hypergraphs [PDF]

A pair of vertices $x$ and $y$ in a graph (or hypergraph) $G$ are said to be resolved by a vertex $w$ if the distance from $x$ to $w$ is not equal to the distance from $y$ to $w$. We say that $G$ is resolved by a set of vertices $W$ if every pair of vertices of $G$ is resolved by some vertex in $W$. The minimum cardinality of a resolving set for $G$ is the metric dimension of $G$. In this talk, we bound the metric dimension of Cayley hypergraphs on finite Abelian groups with the canonical set of generators, and we show that the metric dimension of these hypergraphs is related to the metric dimension of a Cartesian product of circulant graphs. We also present some new results on the metric dimension of circulant graphs. This is joint work with my student Adam Borchert.

KAREN GUNDERSON, University of Bristol Time for graph bootstrap percolation [PDF]

Bootstrap processes are types of cellular automata on graphs with two possible states, called `healthy' and `infected'. For a graph $F$ and a collection of infected edges in a large complete graph, the $F$-bootstrap process is the following update rule for the states of edges: infected edges remain infected forever and a healthy edge becomes infected iff it is the only healthy edge in a copy of $F$. The initial set of infected edges is said to percolate if every edge is eventually infected. The notion of $F$-bootstrap percolation was introduced by Bollobás in 1968 with the name weak-saturation. I will give some of the history of results on the $F$-bootstrap process in the case where the initially infected edges are the edges of an Erdős-Rényi random graph and will discuss some new results on the time to percolation in the $K_r$-bootstrap process when the initially infected edges are chosen randomly.

JEANNETTE JANSSEN, Dalhousie University Uniform linear embeddings of random graphs [PDF]

A symmetric, measurable function $w:[0,1]^2\rightarrow [0,1]$ gives rise to a random graph G(n,w) as follows. Vertices $x_1,\dots ,x_n $ are chosen uniformly at random from $[0,1]$, and each pair of vertices $x_i,x_j$ is joined by an edge with probability $w(x_i,x_j)$, independently. This random graph has a uniform linear embedding if there exist an embedding function $\pi $ and a probability function $f$ so that for all $x,y\in [0,1]$, $w(x,y)=f(|\pi (x)-\pi (y)|)$. In other words, the random graph can be modelled as a process of selecting vertices from $[0,1]$ according to a given distribution described by $\pi$, and adding edges according to a probability that is determined by the distance between the vertices. We explore the question of how to recognize whether a given random graph $G(n,w)$ has a uniform linear embedding. This is joint work with Huda Chuangpishit and Mahya Ghandehari.

DONALD L. KREHER, Michigan Technological University Vertex-Transitive Graphs Of Prime-Squared Order Are Hamilton-Decomposable [PDF]

We prove that all connected vertex-transitive graphs of order $p^2$, p an odd prime, can be decomposed into Hamilton cycles.

(This is joint work with Brian Alspach and Daryn Bryant.)

KAREN MEAGHER, University of Regina Graph Theory and the Erd\H{o}s-Ko-Rado Theorem [PDF]

My favourite theorem is the Erd\H{o}s-Ko-Rado theorem. This theorem is a cornerstone result in extremal set theory that describes the size and structure of the largest intersecting set system. This is the type of problem that makes mathematicians happy; it is easy to understand, the result is exactly what we would hope for, there are many generalizations and a multitude of proofs of this theorem.

In this talk I will focus the different proofs of this result that use graph theory and show how these proofs can be used to prove some of the generalizations of this theorem.

MAGARET-ELLEN MESSINGER, Mt. Allison Elimination Schemes and Lattices [PDF]

Perfect (vertex) elimination schemes are part of characterizations for several graph classes, including chordal and cop-win. Partial elimination schemes reduce a graph to an important subgraph, such as k-cores or robber-win graphs. We are interested in those partial elimination schemes, in which once a vertex is ready to be eliminated, it remains in that state regardless of which other vertices are eliminated. We show that in such a scheme, the sets of subsets of eliminated vertices (when ordered by inclusion) form an upper-locally distributive lattice. We show that process of cleaning graphs and also the cop-win orderings having this property (unless they contain a specific induced subgraph) lead to upper-locally distributive lattices.

*Joint work with R.J. Nowakowski and P. Pralat

JOY MORRIS, University of Lethbridge The isomorphism problem for Cayley graphs [PDF]

It is easy to see that if $\alpha$ is an automorphism of the group $G $, then the Cayley graph Cay$(G;S)$ is isomorphic to the Cayley graph Cay$(G; \alpha(S))$.

A group $G$ has the CI-property if this is the only way to obtain two Cayley graphs on $G$ that are isomorphic. More precisely, $G$ has the CI-property if whenever Cay$(G;S)$ is isomorphic to Cay$(G;T)$, there is a group automorphism $\beta$ of $G$, such that $\beta(S)=T$. The CI-problem is the problem of determining which groups have the CI- property.

I will present an overview of the CI-problem, including some recent developments and open problems.

KIEKA MYNHARDT, University of Victoria Edgeless Graphs are the Only Universal Fixers [PDF]

For any permutation $\pi$ of the vertex set $V(G)$ of a graph $G$, the generalized prism $\pi G$ of $G$ is obtained from two copies $G^{\prime}$ and $G^{\prime\prime}$ of $G$ by joining $u\in V(G^{\prime})$ and $v\in V(G^{\prime\prime})$ if and only if $v=\pi(u)$. Denote the domination number of $G$ by $\gamma(G)$. For all permutations $\pi$ of $V(G)$, $\gamma (G)\leq\gamma(\pi G)\leq2\gamma(G)$. If $\gamma(\pi G)=\gamma(G)$ for all $\pi$, then $G$ is called a universal fixer.

The problem of finding universal fixers was first posed by Diana (Weizhen) Gu [Personal communication to S. T. Hedetniemi, 30th South-Eastern Conference on Graph Theory and Combinatorics, Florida Atlantic University, USA, March 1999], and Mynhardt and Xu [Domination in prisms of graphs: Universal fixers, Utilitas Math. 78(2009), 185-201] conjectured that edgeless graphs are the only universal fixers. This conjecture was recently settled by Kirsti Wash, Clemson University, South Carolina. We present the history and resolution of this conjecture.

DAVID PIKE, Memorial University of Newfoundland Brushing without capacity restrictions [PDF]

We consider a variant of the problem of cleaning a graph with brushes, whereby one vertex is cleaned at a time and there is no restriction on the number of brushes that are permitted to traverse an uncleaned edge. Given a graph $G$, the main question of interest is to determine its brushing number $B(G)$, i.e., the minimum number of brushes that enable the graph to be cleaned. We obtain results for trees and Cartesian products, as well as general upper and lower bounds on the brushing number. This is joint work with Darryn Bryant, Nevena Franceti\'{c}, Przemys\l{}aw Gordinowicz and Pawe\l{} Pra\l{}at.

PAWEL PRALAT, Ryerson University Power of $k$ choices in the process of generating rainbow spanning trees in random graphs [PDF]

We consider the (Erd\H{o}s-R\'enyi) random graph process, which is a stochastic process that starts with $n$ vertices and no edges, and at each step adds one new edge chosen uniformly at random from the set of missing edges. Let $G(n,m)$ be the graph with $m$ edges obtained after $m$ steps of this process. Each edge $e_i$ ($i=1,2,\ldots, m$) of $G(n,m)$ independently chooses precisely $k \in N$ colours, uniformly at random, from a given set of $n-1$ colours (one may view $e_i$ as a multi-edge). We stop the process at the time $M$ when the following two events hold: $G(n,M)$ is connected and every colour occurs at least once. The question is whether $G(n,M)$ has a rainbow (that is, multicoloured) spanning tree. Clearly, both properties are necessary for this property to hold.

In 1994, Frieze and McKay investigated the case $k=1$ and the answer to this question is ``yes'' (asymptotically almost surely). However, since the threshold for connectivity is $\frac {n}{2} \log n$ and the threshold for seeing all the colours is $\frac{n}{k} \log n$, $k=2$ is of special importance. This is a work in progress but I hope to announce that asymptotically almost surely the answer is ``yes'' also for $k \ge 2$.

(Joint work with Deepak Bal, Patrick Bennett, and Alan Frieze.)

MATTHEW SKALA, University of Manitoba Cycle-maximal graphs of fixed girth [PDF]

Among graphs with $n$ vertices and girth at least $g$, which ones contain the most subgraphs that are cycles? This question is more difficult than it sounds. Just counting cycles in one graph is already a $\#P$-complete computational problem closely connected to matrix permanent, and as a theoretical question it connects to difficult open problems in triangle-free graph theory. For $g=3$ the answer is obvious; for $g=4$, we conjecture that evenly balanced complete bipartite graphs are cycle-maximal for all $n$, but only restricted versions of that statement have been proven; and for $g\ge 5$, answers are known by exhaustive search for some small cases but no general pattern has yet emerged. We discuss results on this problem, with an emphasis on the interplay between computational and theoretical work.

Collaboration with Stephane Durocher, David S. Gunderson, and Pak Ching Li.

HENRY WOLKOWICZ, University of Waterloo Coordinate Shadows of Semi-definite and Euclidean Distance Matrix Completions [PDF]

We consider the sets of input data defining feasible semi-definite and Euclidean distance matrix completion problems. We characterize when these sets are closed based on the structure of the underlying graphs, and show that in the presence of boundary data, an intuitive facial reduction technique may drastically reduce the size of the positive semi-definite formulations of these completion problems. We exploit facial reduction based on the cliques of the graph. Chordality of the graph plays an essential role.

collaboration with: Dmitriy Drusvyatskiy, University of Waterloo; Gabor Pataki, University of North Carolina at Chapel Hill

Sponsors