On general frameworks and threshold functions for multiple domination

DOI10.1016/J.DISC.2015.05.003MaRDI QIDQ2352076zbMATH OpenOpenAlexFDO

Authors Vadim Zverovich

Publication date 29 June 2015

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

\(\langle r,s\rangle\)-domination\(\{k\}\)-domination\(k\)-domination\(k\)-tuple dominationparametric dominationthreshold functionstotal \(k\)-dominationupper bounds

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: 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 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.

Recommendations

• Multiple domination
• On upper bounds for multiple domination numbers of graphs
• scientific article; zbMATH DE number 5717271
• Randomized algorithms and upper bounds for multiple domination in graphs and networks
• A generalised upper bound for the k-tuple domination number

Cites work

• \(k\)-domination and \(k\)-independence in graphs: A survey
• A new domination conception
• A note on the k-domination number of a graph
• Dominating a family of graphs with small connected subgraphs
• scientific article; zbMATH DE number 5717271 (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?)
• Improved upper bounds for the k-tuple domination number
• New bounds on the \(k\)-domination number and the \(k\)-tuple domination number
• On domination and annihilation in graphs with claw-free blocks
• On the ratio of optimal integral and fractional covers
• Randomized algorithms and upper bounds for multiple domination in graphs and networks
• The k-tuple domination number revisited
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Transversal numbers of uniform hypergraphs
• Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number

Cited in

(4)

• Randomized algorithms and upper bounds for multiple domination in graphs and networks
• Generalized threshold processes on graphs
• Multiple domination
• A polyhedral view to a generalization of multiple domination

This page was built for publication: On general frameworks and threshold functions for multiple domination

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