On connected \(k\)-domination numbers of graphs.
type: Item
instance of: scholarly article
title: On connected \(k\)-domination numbers of graphs.
zbMATH Open document ID: 1035.05065
DOI: 10.1016/S0012-365X(03)00203-6
author: Shougui Li
published in: Discrete Mathematics
publication date: 2004-01-26T00:00:00Z
review text: A subset \(D\) of the vertex set \(V\) of a graph \(G\) is called a connected \(k\)-dominating set (for a positive integer \(k)\) in \(G\), if for each vertex \(x\in V-D\) there exists a vertex \(y\in D\) such that the distance between \(x\) and \(y\) in \(G\) is at most \(k\) and moreover the subgraph \(G[D]\) of \(G\) induced by \(D\) is conneced. The minimum number of vertices of a connected \(k\)-dominating set in \(G\) is the connected \(k\)-domination number \(\gamma_k^c(G)\) of \(G\) and the maximum number of classes of a partition of \(V\) into connected \(k\)-dominating sets is the connected \(k\)-domatic number \(d^c_k(G)\) of \(G\). The symbol \(\overline G\) denotes the complement of \(G\). The main result of the paper states that if \(k\geq 2\) and both \(G\) and \(\overline G\) are connected, then \(\gamma_k^c(G)\leq(2k+1)d_k^c(G)\).
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 2032870
zbMATH Keywords: Domination number
zbMATH Keywords: Domatic number
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
cites work: The ratio of the distance irredundance and domination numbers of a graph
cites work: Q4368728
cites work: Q4368729
cites work: Q4029974
cites work: An inequality on connected domination parameters
cites work: On $k$-domatic numbers of graphs
cites work: Q3027055
description: scientific article; zbMATH DE number 2032870