Tight upper bounds for the domination numbers of graphs with given order and minimum degree. II

W. Edwin Clark ; Larry A. Dunning ; Stephen Suen

The electronic journal of combinatorics, Tome 7 (2000)

Résumé

Let $\gamma (n,\delta)$ denote the largest possible domination number for a graph of order $n$ and minimum degree $\delta$. This paper is concerned with the behavior of the right side of the sequence $$\gamma (n,0) \ge \gamma (n,1) \ge \cdots \ge \gamma (n,n-1) = 1. $$ We set $ \delta _k(n) = \max \{ \delta \, \vert \, \gamma (n,\delta) \ge k \}$, $k \ge 1.$ Our main result is that for any fixed $k \ge 2$ there is a constant $c_k$ such that for sufficiently large $n$, $$ n-c_kn^{(k-1)/k} \le \delta _{k+1}(n) \le n - n^{(k-1)/k}. $$ The lower bound is obtained by use of circulant graphs. We also show that for $n$ sufficiently large relative to $k$, $\gamma (n,\delta _k(n)) = k$. The case $k=3$ is examined in further detail. The existence of circulant graphs with domination number greater than 2 is related to a kind of difference set in ${\bf Z}_n$.

Détail

DOI : 10.37236/1536

Classification : 05C69, 05C35, 05B10
Mots-clés : dominating set, domination number, minimum degree