Simultaneous Domination in Graphs

Abstract

Let $F_1,F_2,...,F_k$ be graphs with the same vertex set $V$. A subset $S\subseteq V$ is a simultaneous dominating set if for every $i$, $1\le i\le k$, every vertex of $F_i$ not in $S$ is adjacent to a vertex in $S$ in $F_i$; that is, the set $S$ is simultaneously a dominating set in each graph $F_i$. The cardinality of a smallest such set is the simultaneous domination number. We present general upper bounds on the simultaneous domination number. We investigate bounds in special cases, including the cases when the factors, $F_i$, are $r$-regular or the disjoint union of copies of $K_r$. Further we study the case when each factor is a cycle.

References in corpus (2)

• New approach to the $k$-independence number of a graph
• A new bound for the 2/3 conjecture