| Title:
|
The $k$-domatic number of a graph (English) |
| Author:
|
Kämmerling, Karsten |
| Author:
|
Volkmann, Lutz |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
59 |
| Issue:
|
2 |
| Year:
|
2009 |
| Pages:
|
539-550 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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)$. (English) |
| Keyword:
|
domination |
| Keyword:
|
$k$-domination |
| Keyword:
|
$k$-domatic number |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1224.05372 |
| idMR:
|
MR2532389 |
| . |
| Date available:
|
2010-07-20T15:23:00Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140496 |
| . |
| Reference:
|
[1] Cockayne, E. J., Hedetniemi, S. T.: Towards a theory of domination in graphs.Networks 7 (1977), 247-261. MR 0483788, 10.1002/net.3230070305 |
| Reference:
|
[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. Zbl 0573.05049, MR 0812671 |
| Reference:
|
[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. Zbl 0573.05050, MR 0812672 |
| Reference:
|
[4] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs.Marcel Dekker, New York (1998) 233-269. Zbl 0890.05002, MR 1605684 |
| Reference:
|
[5] Haynes, T. W., Hedetniemi, S. T., (eds.), P. J. Slater: Domination in Graphs: Advanced Topics.Marcel Dekker, New York (1998). Zbl 0883.00011, MR 1605685 |
| Reference:
|
[6] Zelinka, B.: Domatic number and degrees of vertices of a graph.Math. Slovaca 33 (1983) 145-147. Zbl 0688.05066, MR 0699083 |
| Reference:
|
[7] Zelinka, B.: Domatic numbers of graphs and their variants: A survey.Marcel Dekker, New York (1998), 351-374. Zbl 0894.05026, MR 1605698 |
| Reference:
|
[8] Zelinka, B.: On k-ply domatic numbers of graphs.Math. Slovaca 34 (1984) 313-318. Zbl 0602.05039, MR 0756989 |
| . |
