Skip to content
DraconiticResearch
Search Sources API
190,332 studies31 sourcesUpdated 10 min ago
PreprintCC BY-NC-ND 4.0arXiv

An improved lower and upper bound of the k-limited domination number

  • Gordana Radić
Open at sourcePDFDOICite

Abstract

We continue the study of k-limited domination in graphs, a domination variant in which each vertex of a dominating set may dominate at most k vertices outside the set. This concept extends classical domination by incorporating capacity constraints on dominating vertices. We improve the general lower bound for the k-limited domination number γkL(G) by employing the concept of k-capacitated domination. As a consequence, we characterize graphs satisfying γkL(G)=⌈ n/(k+1) ⌉. We also refine the known upper bound for graphs with k<δ(G) using the k-limited packing number. Under this condition, we describe graphs attaining γkL(G)=n−k. These results extend and unify previous investigations for the case k=1 and provide a complete characterization of graphs attaining the extreme values of the k-limited domination number under the considered assumptions.

Related

  1. An improved upper bound for the fair domination number of maximal outerplanar graphs
    Yair Caro, Riste Škrekovski
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. An improved upper bound on the chromatic number of the n-dimensional sphere
    A. I. Bikeev, V. A. Voronov, A. M. Raigorodskii
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. An Improved Upper Bound for the Turán Number of the Hexagon
    Sandip Das, Sk Samim Islam, Aashirwad Mohapatra +1
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. An improved lower bound for the packing number of the 2-token graph of the cycle
    Luis Manuel Rivera
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. An improved lower bound for the van der Waerden number w(3,k)
    Haitao Cao
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{radic2026improved,
  title = {{An improved lower and upper bound of the k-limited domination number}},
  author = {Gordana Radić},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.01442},
  eprint = {2610.01442},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.01442},
  note = {CC BY-NC-ND 4.0},
}
RIS
TY  - UNPB
TI  - An improved lower and upper bound of the k-limited domination number
AU  - Gordana Radić
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2610.01442
UR  - https://arxiv.org/abs/2610.01442
AB  - We continue the study of k-limited domination in graphs, a domination variant in which each vertex of a dominating set may dominate at most k vertices outside the set. This concept extends classical domination by incorporating capacity constraints on dominating vertices. We improve the general lower bound for the k-limited domination number γ_k^L(G) by employing the concept of k-capacitated domination. As a consequence, we characterize graphs satisfying γ_k^L(G)=⌈ n/(k+1) ⌉. We also refine the known upper bound for graphs with k<δ(G) using the k-limited packing number. Under this condition, we describe graphs attaining γ_k^L(G)=n−k. These results extend and unify previous investigations for the case k=1 and provide a complete characterization of graphs attaining the extreme values of the k-limited domination number under the considered assumptions.
ER  -