Upper bounds for -domination parameters

DOI10.1007/S00373-009-0864-6MaRDI QIDQ844230zbMATH OpenOpenAlexFDO

Authors Andrei Gagarin, Anush Poghosyan, Vadim Zverovich

Publication date 18 January 2010

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.0612

zbMATH Keywords

\(\alpha \)-domination number\(k\)-tuple domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Stochastic network models in operations research (90B15)

Abstract: In this paper, we provide a new upper bound for the alpha-domination number. This result generalises the well-known Caro-Roditty bound for the domination number of a graph. The same probabilistic construction is used to generalise another well-known upper bound for the classical domination in graphs. We also prove similar upper bounds for the alpha-rate domination number, which combines the concepts of alpha-domination and k-tuple domination.

Recommendations

• On -domination in graphs
• Some remarks on alpha-domination
• Highly connected counterexamples to a conjecture on α -domination
• -domination
• Extremal graphs for a new upper bound on domination parameters in graphs

Cites work

• \(\alpha \)-domination perfect trees
• A generalised upper bound for the k-tuple domination number
• Dominating a family of graphs with small connected subgraphs
• Experiments on data reduction for optimal domination in networks
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 3531438 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Lower Bounds and Algorithms for Dominating Sets in Web Graphs
• On a conjecture of Fink and Jacobson concerning k-domination and k- dependence
• On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
• On the ratio of optimal integral and fractional covers
• Onk-domination and minimum degree in graphs
• The k-tuple domination number revisited

Cited in

(9)

• Multiple domination models for placement of electric vehicle charging stations in road networks
• On -domination in graphs
• Edge-removal and edge-addition in \(\alpha \)-domination
• On -total domination in graphs
• Some remarks on alpha-domination
• A note on \(\alpha\)-total domination in cubic graphs
• Weighted domination models and randomized heuristics
• A denoising diffusion adaptive search for the -domination problem on social graphs
• Onk-tuple domination of random graphs

This page was built for publication: Upper bounds for \(\alpha \)-domination parameters

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