Andrei Gagarin
A generalised upper bound for the k-tuple domination number
Gagarin, Andrei; Zverovich, Vadim
Abstract
In this paper, we provide an upper bound for the k-tuple domination number that generalises known upper bounds for the double and triple domination numbers. We prove that for any graph G,γ× k (G) ≤ frac(ln (δ - k + 2) + ln (∑m = 1k - 1 (k - m) over(d, ^)m + ε{lunate}) + 1, δ - k + 2) n,where γ× k (G) is the k-tuple domination number; δ is the minimal degree; over(d, ^)m is the m-degree of G; ε{lunate} = 1 if k = 1 or 2 and ε{lunate} = - d if k ≥ 3; d is the average degree. © 2007 Elsevier B.V. All rights reserved.
Citation
Gagarin, A., & Zverovich, V. (2008). A generalised upper bound for the k-tuple domination number. Discrete Mathematics, 308(5-6), 880-885. https://doi.org/10.1016/j.disc.2007.07.033
Journal Article Type | Article |
---|---|
Publication Date | Mar 28, 2008 |
Deposit Date | Nov 12, 2010 |
Publicly Available Date | Mar 29, 2024 |
Journal | Discrete Mathematics |
Print ISSN | 0012-365X |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 308 |
Issue | 5-6 |
Pages | 880-885 |
DOI | https://doi.org/10.1016/j.disc.2007.07.033 |
Keywords | graph, domination |
Public URL | https://uwe-repository.worktribe.com/output/1018614 |
Publisher URL | http://dx.doi.org/10.1016/j.disc.2007.07.033 |
Files
A_Generalised_Upper_Bound_for_the_k-Tuple_Domination_Number_-_Revised.pdf
(117 Kb)
PDF
You might also like
Methods of Graph Decompositions
(2022)
Book
Modern Applications of Graph Theory
(2021)
Book
The likelihood of Braess' paradox in traffic networks
(2018)
Book Chapter
Downloadable Citations
About UWE Bristol Research Repository
Administrator e-mail: repository@uwe.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search