Skip to main content

Research Repository

See what's under the surface

On general frameworks and threshold functions for multiple domination

Zverovich, Vadim

Authors



Abstract

© 2015 Elsevier B.V. All rights reserved. We consider two general frameworks for multiple domination, which are called (r,s)-domination and parametric domination. They generalise and unify {k}-domination, k-domination, total k-domination and k-tuple domination. In this paper, known upper bounds for the classical domination are generalised for the (r,s)-domination and parametric domination numbers. These generalisations are based on the probabilistic method and they imply new upper bounds for the {k}-domination and total k-domination numbers. Also, we study threshold functions, which impose additional restrictions on the minimum vertex degree, and present new upper bounds for the aforementioned numbers. Those bounds extend similar known results for k-tuple domination and total k-domination.

Journal Article Type Article
Publication Date Jun 8, 2015
Journal Discrete Mathematics
Print ISSN 0012-365X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 338
Issue 11
Pages 2095-2104
Institution Citation Zverovich, V. (2015). On general frameworks and threshold functions for multiple domination. Discrete Mathematics, 338(11), 2095-2104. https://doi.org/10.1016/j.disc.2015.05.003
DOI https://doi.org/10.1016/j.disc.2015.05.003
Keywords -domination, parametric domination, {k}-domination, k-domination, total k-domination, k-tuple domination, upper bounds, threshold functions
Publisher URL http://dx.doi.org/10.1016/j.disc.2015.05.003
Related Public URLs http://www.sciencedirect.com/science/journal/aip/0012365X

Files







You might also like



Downloadable Citations