Skip to main content

Research Repository

Advanced Search

Upper bounds for α-domination parameters

Gagarin, Andrei; Poghosyan, Anush; Zverovich, Vadim

Upper bounds for α-domination parameters Thumbnail


Authors

Andrei Gagarin

Anush Poghosyan



Abstract

We provide a new upper bound for the α-domination number in terms of a parameter α, 0 < α ≤ 1, and graph vertex degrees. 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. Using a different probabilistic construction, we prove similar upper bounds for the α-rate domination number, which combines the concepts of α-domination and k-tuple domination. © Springer-Verlag 2009.

Citation

Gagarin, A., Poghosyan, A., & Zverovich, V. (2009). Upper bounds for α-domination parameters. Graphs and Combinatorics, 25(4), 513-520. https://doi.org/10.1007/s00373-009-0864-6

Journal Article Type Article
Publication Date Dec 1, 2009
Deposit Date Nov 12, 2010
Publicly Available Date Mar 28, 2024
Journal Graphs and Combinatorics
Print ISSN 0911-0119
Publisher Springer Verlag
Peer Reviewed Peer Reviewed
Volume 25
Issue 4
Pages 513-520
DOI https://doi.org/10.1007/s00373-009-0864-6
Keywords graph, domination, α-Domination, α-rate domination, probabilistic method
Public URL https://uwe-repository.worktribe.com/output/1002607
Publisher URL http://dx.doi.org/10.1007/s00373-009-0864-6
Additional Information Additional Information : The original publication is available at http://dx.doi.org/10.1007/s00373-009-0864-6

Files





You might also like



Downloadable Citations