CMS/SMC
CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013 www.cms.math.ca//2013
       

Domination in Graphs
Organizer and Chair: Gary MacGillivray (University of Victoria)
[PDF]

RICK BREWSTER, Thompson Rivers University
Broadcast domination and its dual multipackings  [PDF] [SLIDES]

Given a graph $G$, a function $f: V \to \{ 0, 1, \dots, \mathrm{diam}(G) \}$ where $f(v) \leq \mathrm{ecc}(v)$ is a \textit{broadcast} and is \textit{dominating} if for each $u$ there is $v$ with $f(v) > 0$ and $\mathrm{dist}(u,v) \leq f(v)$. The cost is $\sum_{v \in V} f(v)$. When $f$ is $\{0,1\}$-valued, the cost is the size of a dominating set. Surprisingly \textit{minimum broadcast domination} is polynomial time solvable. This problem admits a nice integer programming formulation, the dual of which is the maximum multipacking problem. We examine these dual problems, and conditions for equality of optimal solutions.

MICHELLE EDWARDS, University of Victoria
Independent Domination Bicritical Graphs  [PDF]

A graph is independent domination bicritical, or $i$-bicritical, if the removal of any two vertices decreases the independent domination number; that is, if $i(G - \{u,v\}) < i(G)$ for every $\{u,v\} \subseteq V(G)$. A graph is called $i$-superbicritical if the deletion of any two independent vertices reduces the domination number by exactly two; that is, if $i(G-\{u,v\}) = i(G)-2$ for every $\{u,v\}\subseteq V(G)$ where $u$ and $v$ are independent. Structural results and construction techniques for $i$-bicritical graphs will be presented. It can be shown that $i$-superbicritical graphs are also $i$-bicritical, and this special class will be investigated.

STEPHEN FINBOW, St. Francis Xavier
Equality in the Domination Chain in Planar Triangulisations  [PDF] [SLIDES]

Equality in the domination chain, $$ir(G) \le \gamma(G) \le i(G) \le \alpha(G) \le \Gamma(G) \le IR(G),$$ has been extensively studied. In this talk we discuss recent results. In particular, a characterisation of planar triangulations where all minimal dominating sets have the same cardinality and a characterisation of planar triangulations where all six domination parameters are the same will be given. This is joint work with Christopher van Bommel.

RUTH HAAS, Smith College
The k-dominating graph  [PDF]

Given a graph $G$, the {\em $k$-dominating graph of} $G$, $D_k(G)$, is defined to be the graph whose vertices correspond to the dominating sets of $G$ that have cardinality at most $k$. Two vertices in $D_k(G)$ are adjacent if and only if the corresponding dominating sets of $G$ differ by either adding or deleting a single vertex. The graph $D_k(G)$ aids in studying the reconfiguration problem for dominating sets. A key question is determining when two dominating sets are in the same connected component of $D_k(G)$. We give conditions that ensure $D_k(G)$ is connected.

ORTRUD OELLERMANN, University of Winnipeg
Domination and Digital Convexity Parameters  [PDF]

A set $S$ of vertices in a graph $G$ with vertex set $V$ is {\em digitally convex} if for every vertex $v \in V$, $N[v] \subseteq N[S]$ implies $v \in S$. The collection of all digitally convex sets is called the {\em digital convexity} of G. We determine an expression for the Caratheodory number of a graph, with respect to the digital convexity, in terms of a local domination parameter and we find sharp bounds for the Radon number of a graph in terms of two parameters that appear in the well-known domination chain.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Memorial University of Newfoundland