CanaDAM 2021
En ligne, 25 - 28 mai 2021

Broadcasting and Domination

ANNA BACHSTEIN, Clemson University
Compelling Colorings: A generalization of the dominator chromatic number  [PDF]

We define a $\mathcal{P}$-compelling coloring as a proper coloring of the vertices of a graph such that every subset consisting of one vertex of each color has property $\mathcal{P}$. The $\mathcal{P}$-compelling chromatic number is the minimum number of colors in such a coloring. We show that this notion generalizes the dominator and total dominator chromatic numbers, and provide some general bounds and algorithmic results. We also investigate the specific cases where $\mathcal{P}$ is that the subset contains at least one edge or that the subset is connected. Joint work with Wayne Goddard, Michael A. Henning, and John Xue.

KIEKA MYNHARDT, University of Victoria
Boundary independent broadcasts in graphs  [PDF]

A broadcast on a connected graph $G=(V,E)$ is a function $% f:V\rightarrow \{0,1,\dots ,diam(G)\}$ such that $f(v)\leq e(v)$ (the eccentricity of $v$) for all $v\in V$ if $|V|\geq 2$, and $f(v)=1$ if $% V=\{v\}$. If $X$ is an independent set of vertices of $G$, then no edge of $G $ is incident with, or covered by, more than one vertex in $X$. This property generalizes to so-called boundary independent, or bn-independent, broadcasts in which the neighbourhoods of two broadcasting vertices either do not overlap, or overlap only at their boundaries; that is, no edge is covered by more than one broadcasting vertex. The parameters associated with bn-independent broadcasts are $i_{bn}(G)=\min \{\sum_{v\in V}f(v):f$ is a maximal bn-independent broadcast on $G\}$ and $\alpha _{bn% }(G)=\max \{\sum_{v\in V}f(v):f$ is a bn-independent broadcast on $G\}$. We survey recent results concerning $i_{bn}$ and $\alpha _{bn}$.

BRENDAN ROONEY, Rochester Institute of Technology
Efficient $k$-Domination in Hamming Graphs  [PDF]

A \emph{$(j,k)$-dominating function} on $X$ as a function $f:V(X)\rightarrow \{0,\ldots,j\}$ so that for each $v\in V(X)$, $f(N[v])\geq k$, where $N[v]$ is the closed neighbourhood of $v$. Such a function is \emph{efficient} if all of the vertex inequalities are met with equality. They give a simple necessary condition for efficient domination, namely: if $X$ is a $d$-regular graph on $n$ vertices that has an efficient $(1,k)$-dominating function, then the size of the corresponding dominating set divides $n\cdot k$.

The Hamming graph $H(q,d)$ is the graph on the vectors $\mathbb{Z}_q^d$ where two vectors are adjacent if and only if they are at Hamming distance $1$. We show that if $q$ is a prime power, then the previous necessary condition is sufficient for $H(q,d)$ to have an efficient $(1,k)$-dominating function. This result extends a result of Lee from 2001 on independent perfect domination in hypercubes.

AARON SLOBODIN, University of Victoria
2-Limited Broadcast Domination in Grids  [PDF]

Suppose there is a transmitter located at each vertex of a graph $G$. A $k$-limited broadcast on $G$ is an assignment of the integers $0, 1,\dots, k$ to the vertices of $G$. The integer assigned to the vertex $x$ represents the strength of the broadcast from $x$, where strength $0$ means the transmitter at $x$ is not broadcasting. A broadcast of positive strength $s$ from $x$ is heard by all vertices at distance at most $s$ from $x$. A $k$-limited broadcast is called dominating if every vertex assigned $0$ is within distance $d$ of a vertex whose transmitter is broadcasting with strength at least $d$. The $k$-limited broadcast domination number of $G$ is the minimum possible value of the sum of the strengths of the broadcasts in a $k$-limited dominating broadcast of $G$.

We give tight bounds for the $2$-limited broadcast domination number in grids.

VIRGÉLOT VIRGILE, University of Victoria
Eternal domination and clique covering  [PDF]

The eternal domination number of a graph is the minimum number of guards necessary to defend the graph against any sequence of attacks on its vertices. It is well known that the clique covering number of a graph is an upper bound on its eternal domination number. In this talk, we will show that the smallest order of a graph having eternal domination number strictly less than its clique covering number is $10$ and discuss related results.

This is joint work with Gary MacGillivray and Kieka Mynhardt.