CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Broadcasting and Domination

LINO DEMASI, Simon Fraser University
Domination in Plane Triangulations  [PDF]

Matheson and Tarjan showed that the vertices of every plane triangulation can be divided into 3 disjoint sets each of which is dominating. A corollary of this is that any plane triangulation has a dominating set of size $\frac{1}{3} \vert V(G) \vert$. I will present recent work showing that we can obtain a dominating set of size $\frac{2}{7} \vert V(G) \vert$ for all but a few small graphs. This is joint work with Matt Devos.

HAYK GRIGORYAN, Concordia University
On graphs with diametral broadcast time  [PDF]

In this paper we study the family of graphs for which the broadcast time equals to the diameter of the graph. In particular we describe all trees on $n$ vertices with diametral broadcast time. For general graphs we give some partial results. We also look at the broadcast time in graphs with multiple originators and give bounds to estimate the broadcast time. This is joint work with Hovhannes Harutyunyan.

SCOTT LUNNEY, University of Victoria
Broadcasts and Domination in Trees  [PDF]

A broadcast on a graph $G$ is a function $f:V(G)\rightarrow \{0,1,2,...\mathop{\mathrm{diam}}(G)\}$. The broadcast number of $G$ is the minimum value of $\sum_{v\in V}f(v)$ among all broadcasts $f$ for which each vertex of $G$ is within distance $f(v)$ from some vertex $v$ with $f(v)\geq1$. The broadcast number is bounded above by the radius and by the domination number.

I will explore trees for which the broadcast number is equal to its domination number.

HOCINE BOUMEDIENE MEROUANE, Université Saad Dahlab de Blida
The dominator partition in hypercubes  [PDF]

In a graph $G(V,E)$, a vertex $v\in V$ is a dominator of a set $S\subseteq V$ if $S\subseteq N[v]$. $\Pi=\{V_{1},V_{2},..,V_{k}\}$ of $V(G)$ is called dominator partition if every vertex $v\in V$ is a dominator of at least one class $V_{j}$ in $\Pi$. $\pi_{d}(G)$ is the minimum cardinality of a dominator partition of $G$. It is known that $\gamma(G)\leq\pi_{d}(G)\leq\gamma(G)+1$, where $\gamma(G)$ is the domination number of $G$. We show that $\pi_{d}(Qn)=\gamma(Qn)+1$ where $Qn$ is an hypercube.

KAREN SEYFFARTH, University of Calgary
The Dominating Graph  [PDF]

For a graph $G$ and a positive integer $k$, the $k$-dominating graph of $G$, $D_k(G)$, has vertices corresponding to the dominating sets of $G$ with cardinality at most $k$. Two vertices of $D_k(G)$ are joined by an edge if the corresponding sets differ in exactly one element. We explore the question of determining a $k_0(G)$ such that for all $k\geq k_0(G)$, $D_k(G)$ is connected. This is joint work with Ruth Haas.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria