On Alon's problem concerning the difference between connected domination number and domination number
Abstract
For a connected graph G, let γ(G) and γc(G) denote its domination number and connected domination number, respectively. Let M(n,k) be the maximum of γc(G)−γ(G) over all connected n-vertex graphs of minimum degree at least k. Alon proved that 2⌊n/(k+1)⌋−O(1)≤ M(n,k)<n/(k+1) (log⌈log(k+1)⌉+3). He proposed a problem to determine or estimate M(n,k) for n−1≥ k≥ 3, and particularly remarked that it would be interesting to close the loglog(k+1) gap between the upper and lower bounds and decide whether or not M(n,k)=Θ(n/(k+1)). 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 ν=n/(k+1) and Φ(x)= 1/(xlog x/(x−1)) (for x>1). As k→∞, uniformly over all integers n>k+1, M(n,k)= (Φ(ν)+o(1)) νloglog(k+1).
Related
- On Two Questions by Brezis et al Concerning the Critical Difference Quotient Characterization of First-Order Sobolev Spaces
- On the Roots of Connected Domination Polynomials
- On two problems concerning the geodesic transversal number of graphs
- Bounds for the ratio between the independent domination number and the domination number
- On a problem concerning ℤ3-Ramsey numbers
BibTeX
@misc{li2026alons,
title = {{On Alon's problem concerning the difference between connected domination number and domination number}},
author = {Chengli Li and Bo Zhou},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29623},
eprint = {2609.29623},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29623},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On Alon's problem concerning the difference between connected domination number and domination number
AU - Chengli Li
AU - Bo Zhou
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.29623
UR - https://arxiv.org/abs/2609.29623
AB - For a connected graph G, let γ(G) and γ_c(G) denote its domination number and connected domination number, respectively. Let M(n,k) be the maximum of γ_c(G)−γ(G) over all connected n-vertex graphs of minimum degree at least k. Alon proved that 2⌊n/(k+1)⌋−O(1)≤ M(n,k)<n/(k+1) (log⌈log(k+1)⌉+3). He proposed a problem to determine or estimate M(n,k) for n−1≥ k≥ 3, and particularly remarked that it would be interesting to close the loglog(k+1) gap between the upper and lower bounds and decide whether or not M(n,k)=Θ(n/(k+1)). 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 ν=n/(k+1) and Φ(x)= 1/(xlog x/(x−1)) (for x>1). As k→∞, uniformly over all integers n>k+1, M(n,k)= (Φ(ν)+o(1)) νloglog(k+1).
ER -