Tight Upper Bounds for the Domination Numbers of Graphs with Given Order and Minimum Degree, II

W. Edwin Clark and Stephen Suen

               eclark@math.usf.edu   suen@math.usf.edu

Department of Mathematics, University of South Florida, Tampa, FL 33620-5700, USA

Larry A. Dunning

                        dunningk@cs.bgsu.edu

Department of Computer Science, Bowling Green State University Bowling Green, OH 43403-0214, USA

Submitted August 12, 2000, Accepted November 6, 2000

Abstract

Let γ(n, δ) denote the largest possible domination number for a graph of order n and minimum degree δ. This paper is concerned with the behavior of the right side of the sequence

n = γ(n, 0) ≥ γ(n, 1) ≥ ⋯ ≥ γ(n, n − 1) = 1.

We set δ_{k}(n) = max{δ | γ(n, δ) ≥ k}, k ≥ 1. Our main result is that for any fixed k ≥ 2 there is a constant c_{k} such that for sufficiently large n,

n − c_{k}n^{(k−1)/k} ≤ δ_{k+1}(n) ≤ 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, γ(n, δ_{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 ℤ_{n}.

2000 Mathematics Subject Classifications: Primary 05C69, Secondary 05C35

n/δ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1

2 1
3 1 1
4 2 2 1
5 2 2 1 1
6 3 2 2 2 1
7 3 3 2 2 1 1
8 4 4 3 2 2 2 1
9 4 4 3 3 2 2 1 1
10 5 4 3 3 2 2 2 2 1
11 5 5 4 3 3 3 2 2 1 1
12 6 6 4 4 3 3 2 2 2 2 1
13 6 6 4 4 3 3 3 2 2 2 1 1
14 7 6 5 4 4 3 3 3 2 2 2 2 1
15 7 7 5 5 4 *4 3 3 †3 2 2 2 1 1
16 8 8 6 5 *5 4 *4 3 †3 †3 2 2 2 2 1

Table 1: Values of γ(n, δ) for 1 ≤ n ≤ 16. Entries marked with asterisks are unknown. For these cases the best known upper bounds for γ(n, δ) are given. Entries determined in Section 5 are marked by daggers.

1 Introduction

As in [2], we say that a (simple) graph Γ with n vertices and minimum degree δ is an (n, δ)-graph and we define

γ(n, δ) = max{γ(Γ) | Γ is an (n, δ)-graph}

where γ(Γ) denotes the domination number of Γ.

We are interested in the behavior of the right side of the sequence

n = γ(n, 0) ≥ γ(n, 1) ≥ ⋯ ≥ γ(n, n − 1) = 1.  (1.1)

In [2] the values γ(n, δ) for δ = 0, 1, 2, 3 were determined. Table 1 taken from [2] depicts the sequences (1.1) for small values of n. Actually there were six undecided entries in the table given in [2], three of which are decided in Section 5 of this paper. The remaining three unknown entries are marked by asterisks. The values given for these cases are the best known upper bounds.

One easily sees that γ(n, δ) is a non-increasing function in δ. We are interested in determining the numbers δ_{k}(n) where

δ_{k}(n) = max{δ | γ(n, δ) ≥ k}, k ≥ 1.

Since the domination number of an (n, δ)-graph G is 1 if and only if there is a vertex of degree n−1, it is not difficult to see that δ_{1}(n) = n−1 and that for n ≥ 4, δ_{2}(n) ≥ n−2 if n is even while δ_{2}(n) ≥ n − 3 if n is odd. A little reflection shows that these are in fact the actual values of δ_{2}(n) because when n is even, the graph whose complement is a perfect matching is an (n, n − 2)-graph with domination number 2. When n ≥ 5 is odd, the graph whose complement is a Hamilton cycle is an (n, n − 3)-graph with domination number 2. Therefore, for n ≥ 4,

δ_{2}(n) = \{ \begin{matrix}n − 2, & if n is even, \\ n − 3, & if n is odd. \end{matrix}

In this paper, we investigate for each fixed k ≥ 3, the behavior of δ_{k}(n) for all sufficiently large n. We shall also consider the case k = 3 in more detail. There are various known upper bounds of γ(n, δ) (see for example [3]). The upper bound γ^{∗}(n, δ) in Theorem 2 below differs only trivially from the upper bound γ_{6}(n, δ) in [3]. This bound actually gives the exact values of γ(n, δ) for most of the cases under our consideration (see Theorem 7).

Theorem 1 ([3]) Let Λ = δ + 1 if nδ is odd, and let Λ = δ, otherwise. Define the sequence g_{1}, g_{2}, … as follows:

g_{1} = n − Λ − 1 and g_{t+1} = ⌊g_{t} (1 − \frac{δ + 1}{n − t})⌋ , for t ≥ 1.

Set γ^{∗}(n, δ) = min{t | g_{t} = 0}. Then γ(n, δ) ≤ γ^{∗}(n, δ).

Theorem 2 For k ≥ 2, δ_{k+1}(n) < n − n^{(k−1)/k}.

Proof. Assume δ ≥ n − n^{(k−1)/k}. From the fact that

g_{1} < n − δ, and g_{t+1} < g_{t} (\frac{n − δ}{n} ) , t ≥ 1,

we have

g_{k} < n (\frac{n − δ}{n} )^{k} ≤ n(n^{−1/k})^{k} = 1.

Hence g_{k} = 0 and γ(n, δ) ≤ γ^{∗}(n, δ) ≤ k. The theorem therefore follows from the definition of δ_{k+1}(n) which is the maximum value of δ for which γ(n, δ) ≥ k + 1.

We shall show that this upper bound is quite tight in the sense that for all sufficiently large n, there is a constant c_{k} such that

δ_{k+1}(n) ≥ n − c_{k}n^{(k−1)/k}.  (1.2)

Such a lower bound can be established by showing that there exists a graph G with appropriate minimum degree and domination number greater than k. Notice that this is not trivial as our lower bound for δ_{k}(n) is quite close to its upper bound in Theorem 2. We shall in fact construct a circulant graph with the required properties. This requires the construction of a suitably small subset W of the additive group ℤ_{n} = {0, 1, 2, …, n − 1} of integers modulo n with the following property:

ℤ_{n}^{k−1} = ⋃_{w∈W}(w − W)^{k−1},

where for x_{0} ∈ X ⊆ ℤ_{n}, x_{0} − X = {x_{0} − x | x ∈ X} and the superscripts indicate Cartesian set products.

In Sections 4 and 5 we obtain more detailed results in the case of δ_{3}(n). For this it is useful to find circulant graphs of order n with large minimum degree and with domination number at least 3. This turns out to be related to the existence of what we call a symmetric, pseudo difference set, that is, a subset T of ℤ_{n} such that 0 ∉ T, T = −T, and ℤ_{n} = T − T. In Section 4 we prove that if T is a symmetric, pseudo difference set of minimum size then

\sqrt{2}\sqrt{n} − 1 ≤ |T | ≤ 2\sqrt{n} + 3.

2 Circulant graphs with γ > k

We first review the definition of a circulant graph. Let

ℤ_{n} = {0, 1, 2, …, n − 1}

denote the additive group of integers modulo n. For X, Y ⊆ ℤ_{n} we define

−X = {−x | x ∈ X} and X ± Y = {x ± y | x ∈ X, y ∈ Y }.

If S ⊆ ℤ_{n} satisfies the two conditions

0 ∉ S and S = −S  (2.1)

the circulant graph with connection set S is the graph C(n, S) with vertex set ℤ_{n} and adjacency relation ∼ defined by

i ∼ j ⟺ j − i ∈ S.

See Alspach [1] for general results concerning isomorphism of circulant graphs. For each S ⊆ {±1, ±2, …, ±9} Fisher and Spaulding [5] obtained a formula for the domination number of the circulant graph C(S, n) as a function of n and S, but results and techniques do not appear to be useful for our purposes.

Note that the closed neighborhood of a vertex i of C(n, S) is given by

N[ i] = {i} ∪ i + S = {i} ∪ {i + j | j ∈ S}.

To illustrate our construction technique we first consider directed circulant graphs. Suppose R ⊆ ℤ_{n} and 0 ∉ R. Then the circulant digraph with connection set R is the digraph D(n, R) with vertex set ℤ_{n} and directed edges (i, j) whenever j − i ∈ R. Let W = ℤ_{n} − ({0} ∪ R). Notice that i + W is the set of vertices not dominated by vertex i in the digraph D(n, R). Since both C(n, S) and D(n, R) are vertex transitive, we have the following result.

Lemma 1 If R ⊆ ℤ_{n}, 0 ∉ R and W = ℤ_{n} − ({0} ∪ R), then γ(D(n, R)) > k if and only if for all x_{1}, x_{2}, …, x_{k−1} ∈ ℤ_{n}, there exists w_{0}, w_{1}, …, w_{k−1} ∈ W such that w_{0} = x_{i}+w_{i}, for 1 ≤ i ≤ k − 1, that is,

ℤ_{n}^{k−1} = ⋃_{w∈W}(w − W)^{k−1}.  (2.2)

If also W = −W, then R = −R and γ(C(n, R)) > k.

Proof. Since D(n, R) is vertex transitive, we have that γ(D(n, R)) > k if and only if for any x_{1}, x_{2}, …, x_{k−1} ∈ ℤ_{n}, there is a vertex not dominated by any vertex in {0, x_{1}, x_{2}, …, x_{k−1}}. This is equivalent to

W ∩ (x_{1} + W) ∩ … ∩ (x_{k−1} + W) ≠ ∅, for all x_{1}, x_{2}, …, x_{k−1} ∈ ℤ_{n},

which is equivalent to (2.2).

The following theorem gives the existence of suitably small sets W satisfying (2.2) for all fixed k ≥ 2 and all sufficiently large n.

Theorem 3 If k ≥ 2 and let A = a_{1}a_{2} ⋯ a_{k−1} where a_{1}, a_{2}, …, a_{k−1} are pairwise relatively prime integers greater than 1 such that kA < n, there is a subset W of ℤ_{n}−{0} which satisfies equation (2.2) and

|W | ≤ kA + ∑_{i=1}^{k−1} ⌊(n − 1)/a_{i}⌋

Proof. Write

W_{0} = {j | 1 ≤ j ≤ kA},

and for i = 1, 2, …, k − 1,

W_{i} = {ja_{i} | 1 ≤ j ≤ ⌊(n − 1)/a_{i}⌋}.

Let

W = ⋃_{i=0}^{k−1} W_{i}.

We shall show that W satisfies condition (2.2). Let

x_{1}, x_{2}, …, x_{k−1} ∈ {0, 1, 2, …, n − 1}.

Since there are k intervals of the form

I_{j} = {jA + 1, jA + 2, …, (j + 1)A},

where 0 ≤ j ≤ k − 1, there is at least one value of j, say ℓ, such that x_{i} ∉ I_{ℓ}, for i = 1, ⋯, k − 1. For each i, define the indicator

b_{i} = \{ \begin{matrix}0, & x_{i} < ℓA + 1, \\ 1, & x_{i} > (ℓ + 1)A. \end{matrix}

Consider now the system of linear congruences with variable x:

x ≡ x_{i} − b_{i}n (mod a_{i}) 1 ≤ i ≤ k − 1.  (2.3)

Let w_{0} ∈ I_{ℓ} ⊆ W_{0} be a solution for x. From the Chinese Remainder Theorem, it follows that there exists a w_{0} with the required properties. Thus there are integers q_{i} such that

w_{0} = x_{i} − b_{i}n + q_{i}a_{i}, 1 ≤ i ≤ k − 1.

For i = 1, 2, …, k − 1, we define w_{i} = q_{i}a_{i}. We claim that w_{i} ∈ W_{i}. There are two cases. Suppose that x_{i} < ℓA + 1. Then

q_{i}a_{i} = w_{0} − x_{i}, and 0 < w_{0} − x_{i} < n,

which implies that 1 ≤ q_{i} ≤ ⌊(n − 1)/a_{i}⌋. If x_{i} > (ℓ + 1)A, then

q_{i}a_{i} = w_{0} − x_{i} + n, and 0 < n − (x_{j} − w_{0}) < n,

which implies again that 1 ≤ q_{i} ≤ ⌊(n − 1)/a_{i}⌋. Therefore,

w_{i} = q_{i}a_{i} ∈ W_{i},

and in ℤ_{n},

w_{0} = x_{i} − b_{i}n + w_{i} = x_{i} + w_{i}.

We have therefore shown that (2.2) holds. Finally,

|W | ≤ |W_{0}| + ∑_{i=1}^{k−1} |W_{i}| = kA + ∑_{i=1}^{k−1} ⌊(n − 1)/a_{i}⌋.

We next turn our attention to undirected circulant graphs. We could simply take T = W ∪ −W where W is as in the above theorem. Then S = ℤ_{n} − {0} − T provides a connection set for a circulant graph C(n, S) with domination number > k with size at most twice that of W. However, with additional effort we obtain the following somewhat better result.

Theorem 4 Let k ≥ 2 and let A = a_{1}a_{2} ⋯ a_{k−1} where a_{1}, a_{2}, …, a_{k−1} are pairwise relatively prime integers greater than 1 such that ⌈k/2⌉A < n/2. Then there is a subset T of ℤ_{n} − {0} such that T = −T, (2.2) is satisfied and

|T | ≤ 2 ⌈\frac{k}{2}⌉ A + 2 ∑_{i=1}^{k−1} ⌊\frac{n + 2A}{2a_{i}}⌋ .  (2.4)

Proof. Define the set

Q_{0} = {j | 1 ≤ |j| ≤ ⌈k/2⌉A}.

And for i = 1, 2, …, k − 1, define the sets

Q_{i} = {ja_{i}, | 1 ≤ |j| ≤ ⌊(n + 2A)/(2a_{i})⌋}.

Note that we consider the sets Q_{i} to be subsets of ℤ_{n}. Thus to show that an integer u representing an element of ℤ_{n} is in Q_{i} we need to show that u ≡ v (mod n) where v ∈ Q_{i}. Let

T = Q_{0} ∪ Q_{1} ∪ ⋯ ∪ Q_{k−1},

and

x_{1}, x_{2}, …, x_{k−1} ∈ {0, 1, 2, …, n − 1}.

We shall show that there are elements t_{0}, t_{1}, ⋯, t_{k−1} ∈ T such that

x_{i} = t_{0} − t_{i}, i = 1, ⋯, k − 1.

For j = 0, 1, …, ⌈k/2⌉ − 1, let I_{j} be the interval

I_{j} = {jA + 1, jA + 2, …, (j + 1)A}.

Since the 2⌈k/2⌉ intervals ±I_{j}, 0 ≤ j ≤ ⌈k/2⌉ − 1 form a partition of Q_{0} there exists an interval that contains none of the x_{1}, x_{2}, …, x_{k−1}. Since T = −T, we can assume I_{ℓ}, for some ℓ ∈ {0, 1, 2, …, ⌈k/2⌉ − 1}, is such an interval. Define the indicator

b_{i} = \{ \begin{matrix}1, & −n < (ℓ + 1)A − x_{i} ≤ −n/2, \\ 0, & otherwise. \end{matrix}

Consider the system of linear congruences with variable x:

x ≡ x_{i} − b_{i}n (mod a_{i}), 1 ≤ i ≤ k − 1.

By the Chinese Remainder Theorem there is a solution x = t_{0} in the interval I_{ℓ}. Then for some integer q_{i}, we have

t_{0} = x_{i} − b_{i}n + q_{i}a_{i}.

Clearly t_{0} ∈ Q_{0}. We shall next find for each i, t_{i} such that in ℤ_{n},

t_{0} = x_{i} + t_{i}, and t_{i} ∈ Q_{i}.

We consider the following four cases:

(I) n/2 ≤ (ℓ + 1)A − x_{i} < n. This is not possible since

(ℓ + 1)A ≤ ⌈k/2⌉A < n/2.

(II) 0 < (ℓ + 1)A − x_{i} < n/2. Observe that 0 < t_{0} − x_{i} < n/2. Let t_{i} = q_{i}a_{i}. Then

t_{0} = x_{i} + t_{i} = x_{i} + q_{i}a_{i},

and

q_{i} = (t_{0} − x_{i})/a_{i} ∈ (0, n/(2a_{i})),

which implies that t_{i} = q_{i}a_{i} ∈ Q_{i}.

(III) −n/2 < (ℓ + 1)A − x_{i} < 0. In this case we have

t_{0} ≥ ℓA + 1 ≥ (ℓ + 1)A − A.

Then,

t_{0} − x_{i} ≥ (ℓ + 1)A − A − x_{i} > −n/2 − A.

Hence we have −(n + 2A)/2 < t_{0} − x_{i} < 0. Take t_{i} = q_{i}a_{i}. Then since t_{0} = x_{i} + q_{i}a_{i},

q_{i} = (t_{0} − x_{i})/a_{i} ∈ (−(n + 2A)/(2a_{i}), 0),

which implies that t_{i} ∈ Q_{i}.

(IV) −n < (ℓ + 1)A − x_{i} ≤ −n/2. Note that b_{i} = 1 in this case. We also have

t_{0} − x_{i} ≤ (ℓ + 1)A − x_{i} ≤ −n/2

and t_{0} ≥ 1, so −n < t_{0} − x_{i}. Hence

0 < n − (x_{i} − t_{0}) ≤ n/2.

Take t_{i} = −n + q_{i}a_{i}. Then t_{0} = x_{i} − n + q_{i}a_{i} = x_{i} + t_{i}, and

q_{i} = (n − (x_{i} − t_{0}))/a_{i} ∈ (0, n/(2a_{i})],

which implies that q_{i}a_{i} ∈ Q_{i}. Since t_{i} ≡ q_{i}a_{i} (mod n) it follows that t_{i} ∈ Q_{i}. Clearly (2.4) holds. To complete the proof, we note that

|T | ≤ 2 (|Q_{0}| + ∑_{i=1}^{k−1} |Q_{i}|) = 2 ⌈\frac{k}{2}⌉ A + 2 ∑_{i=1}^{k−1} ⌊\frac{n + 2A}{2a_{i}}⌋ .

3 Upper and lower bounds for δ_{k+1}(n)

We assume throughout that k ≥ 2. From [4], Theorem 2, we may choose the pairwise relatively prime integers a_{1}, a_{2}, …, a_{k−1} in Theorem 4 so that for any small ϵ > 0 and for all sufficiently large n,

(1 − ϵ)n^{1/k} ≤ a_{i} ≤ n^{1/k}, 1 ≤ i ≤ k − 1.

Also, if A = a_{1}a_{2} ⋯ a_{k−1} then kA ≤ kn^{(k−1)/k} < n for sufficiently large n. Then

|W | ≤ kA + ∑_{i=1}^{k−1} ⌊(n − 1)/a_{i}⌋
≤ kn^{(k−1)/k} + (k − 1)\frac{n}{(1 − ϵ)n^{1/k}}
= (2k − 1)n^{(k−1)/k} + \frac{(k − 1)ϵ}{1 − ϵ}n^{(k−1)/k}.

Note that by [4], it is possible to have ϵ = Kn^{−1/k} for any increasing function K of n. Also, From (2.2)

ℤ_{n}^{k−1} = ⋃_{w∈W}(w − W)^{k−1},

we have that

n^{k−1} ≤ |W | × |W |^{k−1},

from which we have the following lower bound of |W |:

|W | ≥ n^{(k−1)/k}.

This means that the cardinality of set W constructed above is of the correct order.

Now for the non-directed case, as above, from [4], Theorem 2, we may choose the pairwise relatively prime integers a_{1}, a_{2}, …, a_{k−1} in Theorem 4 so that for any small ϵ > 0 and for all sufficiently large n,

(1 − ϵ)n^{1/k} ≤ a_{i} ≤ n^{1/k}, 1 ≤ i ≤ k − 1,

and

⌈k/2⌉a_{1}a_{2} ⋯ a_{k−1} < n/2.

Then from (2.4) we have

|T | ≤ 2⌈k/2⌉n^{(k−1)/k} + 2(k − 1)\frac{(n + 2n^{(k−1)/k})}{2(1 − ϵ)n^{1/k}}
≤ (k + 1)n^{(k−1)/k} + \frac{(k − 1)(n^{(k−1)/k} + 2n^{(k−2)/k})}{1 − ϵ}
= (2k + \frac{ϵ(k − 1)}{1 − ϵ}) n^{(k−1)/k} + \frac{2(k − 1)}{1 − ϵ}n^{(k−2)/k}.

Thus we have the following theorem.

Theorem 5 For any fixed k ≥ 2, any ϵ > 0 and all sufficiently large n, the following statements hold: (I) There is a circulant digraph H with n vertices, outdegree at least

n − 1 − (2k − 1)n^{(k−1)/k} − \frac{(k − 1)ϵ}{1 − ϵ}n^{(k−1)/k}

and γ(H) > k. (II) There is a circulant graph G with n vertices, degree at least

n − 1 − (2k + \frac{ϵ(k − 1)}{1 − ϵ}) n^{(k−1)/k} − \frac{2(k − 1)}{1 − ϵ}n^{(k−2)/k}

and γ(G) > k.

Combining Theorem 2 and statement (II) in Theorem 5, we have the following estimates for δ_{k+1}(n).

Theorem 6 For any fixed k ≥ 2 and all sufficiently large n,

n − (2k + 1)n^{(k−1)/k} ≤ δ_{k+1}(n) < n − n^{(k−1)/k}.

Note that our lower bound is of the form δ_{k+1}(n) ≥ n − c_{k}n^{(k−1)/k} for some constant c_{k} depending on k. It would be of interest to determine if c_{k} can be replaced by Lk^{α}, for some numbers L and α < 1. In the next section we give better estimates for δ_{3}(n) by dealing directly with the requirement that S = −S (or T = −T).

We next consider the value of γ(n, δ_{k}(n)). It is in general not true that γ(n, δ_{k}(n)) = k. For example, in the sequence {γ(13, δ)}, from Table 1, we have δ_{5}(13) = δ_{6}(13) = 2 and γ(13, 2) = 6. However, one might expect that for any fixed k and for sufficiently large n, γ(n, δ_{k}(n)) = k. This is in fact true, as we now show.

Theorem 7 For all fixed k ≥ 3 and all sufficiently large n, γ(n, δ_{k}(n)) = k.

Proof. From Theorem 6, we have for all sufficiently large n,

δ_{k}(n) ≥ n − (2k + 1)n^{(k−2)/(k−1)}.

Recall also that in our proof of Theorem 2, we see that if δ ≥ n−n^{(k−1)/k} then γ(n, δ) ≤ k. Clearly for all sufficiently large n,

δ_{k}(n) ≥ n − (2k + 1)n^{(k−2)/(k−1)} ≥ n − n^{(k−1)/k},

and thus γ(n, δ_{k}(n)) ≤ k. But γ(n, δ_{k}(n)) ≥ k by definition of δ_{k}(n). The theorem therefore follows.

In the next section we show that if k = 3 then the above theorem holds for n ≥ 6. Note that the results in this section are stated for fixed k and sufficiently large n. In fact, the same results hold if k is a function of n so long as k does not grow too fast with n. For example, the reader can check that Theorems 5 and 6 remain true if k ≤ ln n/(3 ln ln n).

The above results suggest the question: Given n find the largest value K(n) such that for k ≥ K(n), γ(n, δ_{k}(n)) = k. From [2] γ(n, 4) ≥ ⌊n/3⌋ and γ(n, 3) = ⌊3n/8⌋. So for n sufficiently large K(n) ≤ ⌊n/3⌋. More generally we propose the following problem: Given n find the spectrum of values

S(n) = {γ(n, δ) | 0 ≤ δ ≤ n − 1}.

From [2] we know the values of γ(n, δ) for δ = 0, 1, 2, 3. From Theorem 7 we know that there is a function K(n) such that S(n) contains

{i | 1 ≤ i ≤ K(n)}.

4 Circulant Graphs with γ > 2 and Pseudo Difference Sets

When k = 2 from Lemma 1 we obtain:

Lemma 2 Let ℤ_{n} = T ∪S ∪{0} be a partition of ℤ_{n}. Then S = −S and γ(C(n, S)) > 2 if and only if

T = −T and ℤ_{n} = T − T.  (4.1)

Let us say that a subset T of ℤ_{n} is a symmetric, pseudo difference set if the following three conditions hold

(i) 0 ∉ T,

(ii) ℤ_{n} = T − T, and

(iii) T = −T.

We note that in the presence of condition (iii), condition (ii) is equivalent to ℤ_{n} = T + T. Such sets have been studied for general groups and are sometimes called 2-bases for ℤ_{n} (see [7]). On the other hand, a k-subset T of ℤ_{n} is called an (n, k, λ)-difference set if for each non-zero i ∈ ℤ_{n} there are exactly λ ordered pairs (u, v) such that i = u−v (see, for example, [6].) As we will show, one can construct a small symmetric, pseudo difference set using an (n, k, 1) difference set. In this case, n = q^{2} +q +1 where q = k −1 and the corresponding block design is a projective plane of order q. The only known examples are when q is a prime power. It is a famous open question whether or not there exist projective planes of non-prime power order. So we do not expect to be able to use (n, k, 1) difference sets for very many values of n. However, the following lemma shows that we can do quite well for all n, even when an (n, k, 1) difference set does not exist.

We are primarily interested in finding a symmetric, pseudo difference set in ℤ_{n} with the smallest size. From Lemma 2 this will give circulant graphs with large minimum degree and domination number greater than 2.

Lemma 3 There exists a symmetric, pseudo difference set T ⊂ ℤ_{n}, n ≥ 4, such that

|T | ≤ 2 (⌊\frac{\sqrt{n}}{2}⌋ + ⌈\frac{n}{4⌊\frac{\sqrt{n}}{2}⌋}⌉) ≤ 2\sqrt{n} + 3

Proof. Let b be any positive integer satisfying 1 ≤ b ≤ \frac{n}{2}. Define

T_{1}(b) = {1, 2, ⋯, b} ∪ {2ib | i = 1, 2, ⋯, ⌈n/(4b)⌉}.

It is easy to see that

{0, 1, ⋯, ⌊n/2⌋} ⊆ T_{1}(b) ± T_{1}(b).

The critical case is when x = (2i + 1)b + r ≤ n/2 where i and r are positive integers with 0 < r < b. Then x = 2(i + 1)b − (b − r). Hence

i + 1 ≤ \frac{n}{4b} + \frac{1}{2} − \frac{r}{2b} < \frac{n}{4b} + \frac{1}{2}

and i + 1 ≤ ⌈n/(4b)⌉. Thus x ∈ T_{1}(b) − T_{1}(b). It follows that the set

T (b) = T_{1}(b) ∪ −T_{1}(b)

is a symmetric, pseudo difference set. Clearly,

|T (b)| ≤ 2(b + ⌈n/(4b)⌉).

Taking b = ⌊\sqrt{n}/2⌋ we obtain the desired symmetric, pseudo difference set.

In the next lemma we show how to construct symmetric, pseudo difference sets in ℤ_{n} of essentially the same size as that in Lemma 3 if there is an (n, k, 1) difference set.

Lemma 4 If there esists an (n, k, 1) difference set, then there exists a symmetric, pseudo difference set T satisfying

|T | ≤ 2\sqrt{n − 3/4} + 1.

Proof If D is an (n, k, 1) difference set since k(k − 1) = n − 1 we have

|D| = \frac{1 + \sqrt{4n − 3}}{2}.

Since D ≠ ℤ_{n} there is an element a ∈ ℤ_{n} such that a ∉ −D. Then B = a + D is also an (n, k, 1) difference set and 0 ∉ B. Hence T = B ∪ −B is a symmetric, pseudo difference set and

|T | ≤ 2|D| = 1 + \sqrt{4n − 3}.

Lemma 5 If T is a symmetric, pseudo difference set then |T | ≥ \sqrt{2n − 2} ≥ \sqrt{2}\sqrt{n} − 1.

Proof Assume that T does not contain n/2. In this case, T = X ∪ −X where X = {a_{1}, a_{2}, …, a_{s}} and |T | = 2s. Then there are just the following seven types of elements in T − T:

1. a_{i} − a_{j} where i < j,

2. a_{i} − a_{j} where j < i,

3. a_{i} + a_{j} where i < j.

4. −a_{i} − a_{j} where i < j,

5. a_{i} + a_{i},

6. −a_{i} − a_{i},

7. 0 There are at most \binom{s}{2} elements for each of the types (1), (2), (3) and (4). There are at most s elements for each of the types (5) and (6). Since ℤ_{n} = T − T, we must have

4\binom{s}{2} + 2s + 1 ≥ n.

It follows that s ≥ \sqrt{(n − 1)/2}. Hence,

|T | = 2s ≥ 2\sqrt{(n − 1)/2} = \sqrt{2n − 2}.

If n happens to be even and n/2 ∈ T then

T = X ∪ −X ∪ {n/2}

where as above X has s elements a_{1}, a_{2}, …, a_{s}. In this case, in addition to elements of types (1)-(7) above, T − T also contains elements of the form n/2 ± a_{i}. There are at most 2s elements of this type. So we obtain the inequality

4\binom{s}{2} + 2s + 2s + 1 ≥ n.

which gives

|T | = 2s + 1 ≥ \sqrt{2n − 1}.

Since this is larger that the previous bound, we obtain the desired lower bound for |T |.

The following theorem is immediate from Lemmas 3 and 5.

Theorem 8 If T ⊂ ℤ_{n}, n ≥ 6 is a symmetric, pseudo difference set of smallest size then

\sqrt{2}\sqrt{n} − 1 ≤ |T | ≤ 2\sqrt{n} + 3.

Since each such T leads to a circulant graph C(n, S), where S = ℤ_{n} − ({0} ∪ T), with γ(C(n, S)) > 2 we have

Corollary 1 For every positive integer n ≥ 6 there is a circulant graph of order n with domination number at least 3 and minimum degree δ satisfying

n − 2\sqrt{n} − 4 ≤ δ ≤ n − \sqrt{2}\sqrt{n}.

Theorem 9 For n ≥ 4,

n − 2\sqrt{n} − 4 ≤ δ_{3}(n) ≤ n − 3/2 − \sqrt{n − 3/4}.

Proof. From the definition of g_{k} in Theorem 1 we see that

g_{2} ≤ \frac{(n − δ − 1)(n − δ − 2)}{n − 1}.  (4.2)

From Theorem 2, γ(n, δ) ≤ 2 if g_{2} < 1. Let δ = n − x, then the right side (4.2) becomes

\frac{(x − 1)(x − 2)}{n − 1} < 1,  (4.3)

which is equivalent to x < (3 + \sqrt{4n − 3})/2. So if δ > n − \sqrt{n − 3/4} − 3/2 then γ(n, δ) ≤ 2. This gives the desired upper bound for δ_{3}(n). The lower bound follows from Corollary 1. .

Using Theorem 9 we are able to establish the following result.

Theorem 10 If n ≥ 6 then γ(n, δ_{3}(n)) = 3.

Proof. From the definition of δ_{3}(n) we only need to show that for each n ≥ 6 there is some graph Γ of order n with domination number 3. For 6 ≤ n ≤ 16 the result follows directly Table 1. For 16 ≤ n ≤ 150 it is easy to show by straightforward computation that the small symmetric, pseudo difference sets T constructed in Lemma 3 yield circulant graphs with domination number 3. For n > 150, from Theorem 9 it suffices to prove that if δ ≥ n − 2\sqrt{n} − 4 then γ(n, δ) ≤ 3. From Theorem 1 we only need to show for δ ≥ n − 2\sqrt{n} − 4 and n > 150 that g_{3} < 1. Now

g_{3} ≤ \frac{(n − δ − 1)(n − δ − 2)(n − δ − 3)}{(n − 1)(n − 2)}
≤ \frac{(n − δ − 1)^{3}}{(n − 2)^{2}}
≤ \frac{(2\sqrt{n} + 3)^{3}}{(n − 2)^{2}} .

It is easy to see that

φ(n) = \frac{(2\sqrt{n} + 3)^{3}}{(n − 2)^{2}}

is a decreasing function for n > 2 so it suffices to calculate

φ(150) = \frac{1}{39601} (2 \sqrt{150} + 3)^{3} ≈ .5248680758 < 1.

5 Exact values of δ_{3}(n) for small n.

In this section we give exact values of δ_{3}(n) for 6 ≤ n ≤ 16 and for n = 19. This entails showing that γ(15, 9) = 3, γ(16, 10) = 3, and γ(19, 12) = 3. We also show that γ(16, 9) = 3. This fills in three of the six unknown entries in the table of values of γ(n, δ) in [2]. The following table gives known values for δ_{3}(n) for 6 ≤ n ≤ 16 and n = 10. (Note that for n ≤ 5, γ(n, δ) ≤ 2.)

\begin{matrix}n & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 19 \\ δ_{3}(n) & 1 & 2 & 3 & 4 & 4 & 6 & 6 & 7 & 8 & 9 & 10 & 12 \end{matrix}

Exact values of δ_{3}(n) for 6 ≤ n ≤ 14 are given in [2]. Since γ(15, 10) = 2 and γ(16, 11) = 2 by [2], to show that δ_{3}(15) = 9 and δ_{3}(16) = 10 it suffices to exhibit a (15, 9)-graph with domination number 3 and a (16, 10)-graph with domination number 3. The following is an adjacency list for a (15, 9)-graph with domination number 3. The vertex set is {0, 1, 2, …, 14}. Note that all vertices have degree 9 except for vertex 14 which has degree 10.

0 1 5 6 7 9 11 12 13 14
1 0 2 6 8 9 10 11 13 14
2 1 3 7 8 9 10 12 13 14
3 2 4 6 7 9 10 11 12 14
4 3 5 6 8 9 10 12 13 14
5 0 4 7 8 9 10 11 13 14
6 0 1 3 4 8 10 12 13 14
7 0 2 3 5 8 10 11 13 14
8 1 2 4 5 6 7 11 12 14
9 0 1 2 3 4 5 11 12 14
10 1 2 3 4 5 6 7 11 13
11 0 1 3 5 7 8 9 10 12
12 0 2 3 4 6 8 9 11 13
13 0 1 2 4 5 6 7 10 12
14 0 1 2 3 4 5 6 7 8 9

There is no (16, 10)-circulant graph with domination number 3. However, we were able to find a Cayley graph on the semi-dihedral group of order 16 with δ = 10 and γ = 3 showing that γ(16, 10) = 3 and δ_{3}(16) = 10. Again, if we take the vertex set to be the integers {0, 1, 2, …, 15}, the adjacency list of the graph is:

0 2 3 4 7 8 9 14 13 5 1
1 2 3 4 6 8 9 15 12 5 0
2 3 4 6 7 10 11 15 13 0 1
3 2 6 7 10 11 14 12 5 0 1
4 2 6 7 9 11 12 13 5 0 1
5 3 4 6 7 8 10 12 13 0 1
6 2 3 4 7 8 11 14 15 5 1
7 2 3 4 6 9 10 14 15 5 0
8 6 9 10 11 14 15 13 5 0 1
9 4 7 8 10 11 14 15 12 0 1
10 2 3 7 8 9 11 15 12 13 5
11 2 3 4 6 8 9 10 14 12 13
12 3 4 9 10 11 14 15 13 5 1
13 2 4 8 10 11 14 15 12 5 0
14 3 6 7 8 9 11 15 12 13 0
15 2 6 7 8 9 10 14 12 13 1

We have one additional exact value of δ_{3}(n), namely, δ_{3}(19) = 12: A complete search of circulant graphs of order n ≤ 50 finds the (19, 12)-graph C(19, S_{1}) where

S_{1} = {1, 4, 6, 7, 8, 9, 10, 11, 12, 13, 15, 18}

such that γ(C(19, S_{1})) = 3, showing that δ_{3}(19) = 12, since γ^{∗}(19, 12) ≤ 3 and γ^{∗}(19, 13) = 2.

We also mention here the (16, 9)-graph C(16, S_{2}) where

S_{2} = {1, 2, 3, 6, 8, 10, 13, 14, 15}

which has domination number 3. This shows that γ(16, 9) = 3, thereby filling another missing entry in the table of values of γ(n, δ) in [2]

Acknowledgement We wish to thank Gordon Royle for providing Cayley tables for the 14 groups of order 16 and Cayley graphs of groups of orders up to 31.

References

[1] Brian Alspach, Isomorphism and Cayley Graphs on Abelian Groups, Graph symmetry (Montreal, PQ, 1996), 1–22, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 497, Kluwer Acad. Publ., Dordrecht, 1997.

[2] W. Edwin Clark and Larry A. Dunning, Tight Upper Bounds for the Domination Numbers of Graphs with Given Order and Minimum Degree, Electron. J. Combin. 4 (1997), no. 1, Research Paper 26, 1–25.

[3] W. Edwin Clark, David Fisher, Boris Shekhtman, and Stephen Suen, Upperbounds of the Domination Number of a Graph, Congr. Numer., 132 (1998), 99-123.

[4] Paul Erdös and J. L. Selfridge, Complete prime subsets of consecutive integers, Proceedings of the Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man. , 1971), pp. 1–14. Dept. Comput. Sci., Univ. Manitoba, Winnipeg, Man., 1971.

[5] David C Fisher and Anne Spalding, Domination of circulant graphs: an example of min-plus algebra. Proceedings of the Twenty-eighth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1997). Congr. Numer. 128 (1977), 45–54.

[6] Marshall Hall, Jr. Combinatorial Theory, Blaisdell Pub. Co.,Waltham Mass., 1967.

[7] X. D. Jia, Thin Bases for Finite Abelian Groups J. of Number Theory, 36 (1990) , 254–256.