Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
domination; $k$-domination; $k$-domatic number
domination; $k$-domination; $k$-domatic number
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)$.
References:
[1] Cockayne, E. J., Hedetniemi, S. T.: Towards a theory of domination in graphs. Networks 7 (1977), 247-261. DOI 10.1002/net.3230070305 | MR 0483788
[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 0812671 | Zbl 0573.05049
[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 0812672 | Zbl 0573.05050
[4] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998) 233-269. MR 1605684 | Zbl 0890.05002
[5] Haynes, T. W., Hedetniemi, S. T., (eds.), P. J. Slater: Domination in Graphs: Advanced Topics. Marcel Dekker, New York (1998). MR 1605685 | Zbl 0883.00011
[6] Zelinka, B.: Domatic number and degrees of vertices of a graph. Math. Slovaca 33 (1983) 145-147. MR 0699083 | Zbl 0688.05066
[7] Zelinka, B.: Domatic numbers of graphs and their variants: A survey. Marcel Dekker, New York (1998), 351-374. MR 1605698 | Zbl 0894.05026
[8] Zelinka, B.: On k-ply domatic numbers of graphs. Math. Slovaca 34 (1984) 313-318. MR 0756989 | Zbl 0602.05039
Search
Partner of
