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/

[1] Cockayne, E. J., Hedetniemi, S. T.: Towards a theory of domination in graphs. Networks 7 (1977), 247-261. | DOI | MR

[2] Fink, J. F., Jacobson, M. S.: $n$-domination in graphs. Graph Theory with Applications to Algorithms and Computer Science. John Wiley and Sons, New York (1985) 282-300. | MR | Zbl

[3] Fink, J. F., Jacobson, M. S.: On $n$-domination, $n$-dependence and forbidden subgraphs. Graph Theory with Applications to Algorithms and Computer Science. John Wiley and Sons, New York (1985) 301-311. | MR | Zbl

[4] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998) 233-269. | MR | Zbl

[5] Haynes, T. W., Hedetniemi, S. T., (eds.), P. J. Slater: Domination in Graphs: Advanced Topics. Marcel Dekker, New York (1998). | MR | Zbl

[6] Zelinka, B.: Domatic number and degrees of vertices of a graph. Math. Slovaca 33 (1983) 145-147. | MR | Zbl

[7] Zelinka, B.: Domatic numbers of graphs and their variants: A survey. Marcel Dekker, New York (1998), 351-374. | MR | Zbl

[8] Zelinka, B.: On k-ply domatic numbers of graphs. Math. Slovaca 34 (1984) 313-318. | MR | Zbl