Metraipolis › archive › dc_b7cbfdd06c64
On Alon's problem concerning the difference between connected domination number and domination number — arXiv:2609.29623
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.29623
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T06:40:57.157Z
- SHA-256 of the archived text
72ed8e6ac9ccd17f7e7d2958cfb621da736d662293880114e8fa4b1bded64a2e- Stable URL of this page
https://metraipolis.com/documento/dc_b7cbfdd06c64
How to cite
On Alon's problem concerning the difference between connected domination number and domination number — arXiv:2609.29623 — arXiv (en), https://arxiv.org/abs/2609.29623 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b7cbfdd06c64 (Metraipolis archive dc_b7cbfdd06c64, sha256 72ed8e6ac9ccd17f7e7d2958cfb621da736d662293880114e8fa4b1bded64a2e)
BibTeX
@misc{dcb7cbfdd06c64,
title = {On Alon's problem concerning the difference between connected domination number and domination number — arXiv:2609.29623},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.29623},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b7cbfdd06c64; sha256 72ed8e6ac9ccd17f7e7d2958cfb621da736d662293880114e8fa4b1bded64a2e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.29623. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
For a connected graph $G$, let $\gamma(G)$ and $\gamma_c(G)$ denote its domination number and connected domination number, respectively. Let $M(n,k)$ be the maximum of $\gamma_c(G)-\gamma(G)$ over all connected $n$-vertex graphs of minimum degree at least $k$. Alon proved that \[ 2\left\lfloor\frac{n}{k+1}\right\rfloor-O(1)\le M(n,k)<\frac{n}{k+1} \bigl(\log\lceil\log(k+1)\rceil+3\bigr). \] He proposed a problem to determine or estimate $M(n,k)$ for $n-1\ge k\ge 3$, and particularly remarked that it would be interesting to close the $\log\log(k+1)$ gap between the upper and lower bounds and decide whether or not $M(n,k)=\Theta\bigl(\frac{n}{k+1}\bigr)$. We give an asymptotic answer to Alon's problem for sufficiently large $k$. More precisely, $M(k+1,k)=0$. For $n>k+1$, let \[ \nu=\frac{n}{k+1} \text{ and } \Phi(x)= \frac{1}{x\log\!\frac{x}{x-1}} \ (\text{for }x>1). \] As $k\to\infty$, uniformly over all integers $n>k+1$, \[ M(n,k)= \big(\Phi(\nu)+o(1)\big) \nu\log\log(k+1). \]
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-25 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.29623 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T06:02:10.056Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).