Geodesic
The $k$-domatic number of a graph
Czechoslovak Mathematical Journal, Tome 59 (2009) no. 2, pp. 539-550 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $k$ be a positive integer, and let $G$ be a simple graph with vertex set $V(G)$. A {\it $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 {\it $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 {\it $k$-domatic number} $d_k(G)$. \endgraf 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)$.
Let $k$ be a positive integer, and let $G$ be a simple graph with vertex set $V(G)$. A {\it $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 {\it $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 {\it $k$-domatic number} $d_k(G)$. \endgraf 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)$.
Classification : 05C69
Keywords: domination; $k$-domination; $k$-domatic number 
@article{CMJ_2009_59_2_a16,
     author = {K\"ammerling, Karsten and Volkmann, Lutz},
     title = {The $k$-domatic number of a graph},
     journal = {Czechoslovak Mathematical Journal},
     pages = {539--550},
     year = {2009},
     volume = {59},
     number = {2},
     mrnumber = {2532389},
     zbl = {1224.05372},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2009_59_2_a16/}
}
TY  - JOUR
AU  - Kämmerling, Karsten
AU  - Volkmann, Lutz
TI  - The $k$-domatic number of a graph
JO  - Czechoslovak Mathematical Journal
PY  - 2009
SP  - 539
EP  - 550
VL  - 59
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2009_59_2_a16/
LA  - en
ID  - CMJ_2009_59_2_a16
ER  - 
%0 Journal Article
%A Kämmerling, Karsten
%A Volkmann, Lutz
%T The $k$-domatic number of a graph
%J Czechoslovak Mathematical Journal
%D 2009
%P 539-550
%V 59
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2009_59_2_a16/
%G en
%F CMJ_2009_59_2_a16
Kämmerling, Karsten; Volkmann, Lutz. The $k$-domatic number of a graph. Czechoslovak Mathematical Journal, Tome 59 (2009) no. 2, pp. 539-550. http://geodesic.mathdoc.fr/item/CMJ_2009_59_2_a16/