CanaDAM 2015
Université de la Saskatchewan, 1 - 4 juin 2015

Independence and domination

MICHAEL BARRUS, University of Rhode Island
Graph Classes with Near-Equality of Independence Numbers and Havel--Hakimi Residues  [PDF]

The residue $r(G)$ of a graph $G$ is the number of zeros remaining upon completion of the Havel--Hakimi algorithm on the degree sequence of $G$. It is one of the best known lower bounds on the independence number $\alpha(G)$ of a graph in terms of the degree sequence, though the bound may be arbitrarily weak. We describe progress in characterizing the maximal hereditary class $\mathcal{H}$ of graphs $G$ for which $r(G) =\alpha(G)$. In particular, we determine all minimal forbidden subgraphs of $\mathcal{H}$ having order at most $10$ and show that various (nearly-)hereditary families belong to $\mathcal{H}$ (or nearly do).

MICHELLE EDWARDS, University of Victoria
The Number of Minimum Dominating Sets of a Tree  [PDF]

We present an upper bound on the number of minimum dominating sets of a tree in terms of the domination number, which in turn can be used to give an upper bound in terms of order. This bound is compared to known bounds for the number of minimal dominating sets of a tree. We also show a family of trees that possess many minimum dominating sets, thus answering a question posed by Fricke, Hedetniemi, Hedetniemi, and Hutson regarding the order of the gamma graph of a tree. Additional results concerning the gamma graph are also discussed.

MOHSEN MOLLAHAJIAGHAEI, University of Western Ontario
Independent and domination number of simplicial rook graphs  [PDF]

Let $\mathbb{N}_{0}=\mathbb{N}\cup\{0\}$. The simplicial rook graph, denoted by $SR(m,n)$ is the graph of which the vertices are the vectors in $\mathbb{N}_{0}^{m}$ summing to $n$, where two vectors are adjacent when they differ in precisely two coordinates. The independent number of $SR(m,n)$ is the maximum number of non-attacking rooks on a simplicial-chessboard. We give a partial solution for this number. Also, we provide lower and upper bounds for $\alpha(SR(m,n))$.\newline The domination number of this graph is the smallest number of rooks that can dominate a simplicial-chessboard. We prove that $\gamma(SR(3,n))=[n/2]+1$. In general, we show that $\gamma(SR(m,n))=\theta(n^{m-2})$.\newline (Joint work with Arash-Ahadi)

FEIRAN YANG, University of Victoria
Old and new results on broadcast domination and multipacking  [PDF]

A dominating broadcast is a function $f: V \to \{0, 1,\ldots,\mathit{rad}(G)\}$ such that for every vertex $u \in V$ we have $d(u, x) \leq f(x)$ for some vertex $x$ with $f(x) > 0$. The dual of broadcast domination is multipacking, which is a subset $S \subseteq V$ such that for every vertex $x$ and each $i = 1, 2,\ldots$, the ball of radius $i$ about $x$ contains at most $i$ vertices of $S$. We will begin by discussing algorithms for minimum broadcast domination and maximum multipacking on strongly chordal graphs, and trees in particular, and then discuss further directions.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Saskatchewan