Probabilistic analysis of upper bounds for 2-connected distance \(k\)-dominating sets in graphs

DOI10.1016/j.tcs.2009.05.028zbMath1171.68032MaRDI QIDQ837173

Fang Tian, Jun-Ming Xu, Zi-Long Liu

Publication date: 10 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.028

zbMATH Keywords

fault tolerance; wireless networks; connected dominating set; Chernoff inequality

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68M15: Reliability, testing and fault tolerance of networks and computer systems

Related Items

On bondage numbers of graphs: a survey with some comments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The \(k\)-tuple domination number revisited
• Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem
• The diversity of domination
• 2-connected graphs with small 2-connected dominating sets.
• On \(\alpha_{r}\gamma_{s}(k)\)-perfect graphs
• On connected \(k\)-domination numbers of graphs.
• Distance paired domination numbers of graphs
• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
• New bounds on the \(k\)-domination number and the \(k\)-tuple domination number
• On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
• Paths in graphs