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

DOI10.1016/J.TCS.2009.05.028MaRDI QIDQ837173zbMATH OpenOpenAlexFDO

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

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

Chernoff inequalityconnected dominating setfault tolerancewireless networks

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Reliability, testing and fault tolerance of networks and computer systems (68M15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• New probabilistic upper bounds on the domination number of a graph
• Bounds on probability of connectedness of a random graph
• Bounds on the distance two-domination number of a graph
• Near-optimal dominating sets in dense random graphs in polynomial expected time
• Approximating k-Connected m-Dominating Sets
• Approximating \(k\)-connected \(m\)-dominating sets
• Lower bounds of connectedness probability for some classes of random graphs
• Lower bounds on the probability of connectedness in classes of random graphs generated by 2-connected graphs with a given base spectrum
• Bounds for distance domination numbers of graphs
• Bounds on the connected \(k\)-domination number in graphs

Cites work

• 2-connected graphs with small 2-connected dominating sets.
• Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem
• Distance paired domination numbers of graphs
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• New bounds on the \(k\)-domination number and the \(k\)-tuple domination number
• On \(\alpha_{r}\gamma_{s}(k)\)-perfect graphs
• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
• On connected k-domination numbers of graphs.
• On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
• On distance connected domination numbers of graphs.
• Paths in graphs
• The k-tuple domination number revisited
• The diversity of domination

Cited in

(1)

• On bondage numbers of graphs: a survey with some comments

This page was built for publication: Probabilistic analysis of upper bounds for 2-connected distance \(k\)-dominating sets in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q837173)