Skip to content
DraconiticResearch
Search Sources API
182,549 studies31 sourcesUpdated 8 min ago
PreprintarXiv licencearXiv

Bounds for the ratio between the independent domination number and the domination number

  • Gunnar Brinkmann
  • Steven Van Overberghe
Open at sourcePDFDOICite

Abstract

In this article we present new and improved results for the ratio between the independent domination number and the domination number in graphs with bounded degree. We present a general formula, that, for a fixed maximum degree, allows to compute an upper bound for this ratio as a function of an upper bound β|V| for the independent domination number. We also apply this formula to several known upper bounds for the independent domination number. Furthermore we present constructions giving lower bounds for the best possible upper bound in various classes of graphs with bounded degree.

Related

  1. An inequality for the number of independent sets of matroids with an application to the forest-tree ratio of graphs
    Ferenc Bencs, Péter Csikvári
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. On Alon's problem concerning the difference between connected domination number and domination number
    Chengli Li, Bo Zhou
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Independent domination in central graphs
    Abel Cabrera-Martínez, José Luis López-Carmona, Ismael Rios-Villamar +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. On the (independent) semitotal domination in subdivision, middle, and central graphs
    Abel Cabrera-Martínez, José Luis López-Carmona, Ismael Rios-Villamar +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. The domination number of the $2$-token graph of path graphs
    Emmanuel Acosta Troncoso, Luis Manuel Rivera
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{brinkmann2026bounds,
  title = {{Bounds for the ratio between the independent domination number and the domination number}},
  author = {Gunnar Brinkmann and Steven Van Overberghe},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2606.16698},
  eprint = {2606.16698},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.16698},
}
RIS
TY  - UNPB
TI  - Bounds for the ratio between the independent domination number and the domination number
AU  - Gunnar Brinkmann
AU  - Steven Van Overberghe
PY  - 2026
DA  - 2026/09/29
PB  - arXiv
DO  - 10.48550/arxiv.2606.16698
UR  - https://arxiv.org/abs/2606.16698
AB  - In this article we present new and improved results for the ratio between the independent domination number and the domination number in graphs with bounded degree. We present a general formula, that, for a fixed maximum degree, allows to compute an upper bound for this ratio as a function of an upper bound β|V| for the independent domination number. We also apply this formula to several known upper bounds for the independent domination number. Furthermore we present constructions giving lower bounds for the best possible upper bound in various classes of graphs with bounded degree.
ER  -