Karsten Kammerling, Lutz Volkmann, Lehrstuhl II fur Mathematik, RWTH Aachen University, 52056 Aachen, Germany, e-mail: volkm@math2.
rwth-aachen.de
Abstract: Let $k$ be a positive integer, and let $G$ be a simple graph with vertex set $V(G)$. A $k$-dominating set of the graph $G$ is a subset $D$ of $V(G)$ such that every vertex of $V(G)-D$ is adjacent to at least $k$ vertices in $D$. A $k$-domatic partition of $G$ is a partition of $V(G)$ into $k$-dominating sets. The maximum number of dominating sets in a $k$-domatic partition of $G$ is called the $k$-domatic number $d_k(G)$. In this paper, we present upper and lower bounds for the $k$-domatic number, and we establish Nordhaus-Gaddum-type results. Some of our results extend those for the classical domatic number $d(G)=d_1(G)$.
Keywords: domination, $k$-domination, $k$-domatic number
Classification (MSC 2000): 05C69
Full text available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).
Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade.
To activate your access, please contact Myris Trade at myris@myris.cz.
Subscribers of Springer need to access the articles on their site, which is http://www.springeronline.com/10587.
