Upper bounds for α-domination parameters

Gagarin, Andrei; Poghosyan, Anush; Zverovich, Vadim

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.

• Journal Article Type: Article
• Publication Date: Dec 1, 2009
• Deposit Date: Nov 12, 2010
• Publicly Available Date: Oct 27, 2016
• Journal: Graphs and Combinatorics
• Print ISSN: 0911-0119
• Electronic ISSN: 1435-5914
• 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
• Contract Date: Oct 27, 2016