TIGHT UPPER BOUNDS FOR THE DOMINATION NUMBERS

OF GRAPHS WITH GIVEN ORDER AND MINIMUM DEGREE

W. Edwin Clark University of South Florida Tampa, FL 33620-5700 eclark@math.usf.edu and Larry A. Dunning Bowling Green State University Bowling Green, OH 43403-0214 dunning@cs.bgsu.edu

Submitted: June 2, 1997; Accepted: October 27, 1997

Abstract. Let γ(n, δ) denote the maximum possible domination number of a graph with n vertices and minimum degree δ. Using known results we determine γ(n, δ) for δ = 0, 1, 2, 3, n ≥ δ + 1 and for all n, δ where δ = n − k and n is sufficiently large relative to k. We also obtain γ(n, δ) for all remaining values of (n, δ) when n ≤ 14 and all but 6 values of (n, δ) when n = 15 or 16.

1. Introduction

We denote the domination number of a graph G by γ(G). By an (n, δ)-graph we

mean a graph with n vertices and minimum degree δ. Let γ(n, δ) be the maximum

of γ(G) where G is an (n, δ)-graph. Using known results [3,7,8,9] one easily finds

the exact values of γ(n, δ) when δ = 0, 1, 2, 3. It is also fairly easy to obtain γ(n, δ)

when δ = n − k for n sufficiently large relative to k. By various methods we also

find γ(n, δ) for all remaining values of (n, δ) when n ≤ 14 and all but 6 values of

(n, δ) when n = 15 and 16. Many values can be established using the upper bounds

in [2] together with examples found by computer search or ad hoc techniques. In a

number of cases we have used Brendan McKay’s program makeg [6] to generate all

Typeset by AMS-TEX the electronic journal of combinatorics 4 (1997), #R26 2

1991 Mathematics Subject Classification. 05C35.

Key words and phrases. graph, domination number, upper bounds, minimum degree.

nonisomorphic (n, δ)-graphs while checking the domination numbers using a simple recursive, depth-first search.

Our results give support to the the natural conjecture that γ(n, δ) is attained by an (n, δ)-graph with the minimum number of edges, that is, by a regular graph if nδ is even or by a graph with degree sequence (δ +1, δ, δ, …, δ) if nδ is odd. We are able to verify the conjecture for all the cases mentioned above where we are able to determine γ(n, δ) and in at least one case where we are not (see Proposition 4.11). However, see Section 5 for some evidence in oppostion to the conjecture.

To simplify discussion we say that a graph is almost δ-regular if its degree sequence has the form (δ + 1, δ, δ, …, δ) and we define γ_{r}(n, δ) to be the maximum of γ(G) where G is an (n, δ)-graph which is regular if nδ is even and almost regular if nδ is odd. In this notation the above mentioned conjecture becomes γ(n, δ) = γ_{r}(n, δ) for all n and δ.

We use the following standard notation. Let G = (V, E) be a graph with vertex set V and edge set E. We write x ∼ y to indicate that the vertices x and y are adjacent. For v ∈ V the open neighborhood N(v) is the set of all vertices adjacent to v and the closed neighborhood of v is the set N[v] = N(v) ∪ {v}. S ⊆ V is a dominating set for G if ⋃_{x∈S} N[x] = V. The domination number, γ(G), is the cardinality of a smallest dominating set for G. If x ∼ y or x = y we say that x covers y. If A ⊆ V then we let ⟨A⟩ denote the subgraph of G induced by A.

Table 1 contains the value of γ(n, δ) for n ≤ 16, 0 ≤ δ ≤ n − 1 if the value is known, otherwise upper and lower bounds for γ(n, δ). We establish these values in Sections 2, 3 and 4.

Table 1. Values of γ(n, δ) for n ≤ 16, 0 ≤ δ ≤ n − 1.
n ⧹ δ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1  1
2  2 1
3  3 1 1
4  4 2 2 1
5  5 2 2 1 1
6  6 3 2 2 2 1
7  7 3 3 2 2 1 1
8  8 4 4 3 2 2 2 1
9  9 4 4 3 3 2 2 1 1
10  10 5 4 3 3 2 2 2 2 1
11  11 5 5 4 3 3 3 2 2 1 1
12  12 6 6 4 4 3 3 2 2 2 2 1
13  13 6 6 4 4 3 3 3 2 2 2 1 1
14  14 7 6 5 4 4 3 3 3 2 2 2 2 1
15  15 7 7 5 5 4 3-4 3 3 2-3 2 2 2 1 1
16  16 8 8 6 5 4-5 4 3-4 3 2-3 2-3 2 2 2 2 1

2. The cases δ = 0, 1, 2, 3.

Lemma 2.1. If n ≥ m > δ ≥ 1 then

(2.1)  γ(n, δ) + γ(m, δ) ≤ γ(n + m, δ)

and if nδ or mδ is even

(2.2)  γ_{r}(n, δ) + γ_{r}(m, δ) ≤ γ_{r}(n + m, δ).

Proof. The lemma is immediate from the fact that if G is an (n, δ)-graph and H is an (m, δ)-graph then the disjoint union G ∪ H is an (n + m, δ)-graph with

the electronic journal of combinatorics 4 (1997), #R26 4

domination number γ(G ∪ H) = γ(G) + γ(H). (2.2) follows from the fact that if G is regular and H is regular (resp., almost regular) then G ∪ H is regular (resp., almost regular). □ Corollary 2.2. For every positive integer k we have

(2.2)  kγ(n, δ) ≤ γ(kn, δ)

and provided that nδ is even,

(2.3)  kγ_{r}(n, δ) ≤ γ_{r}(kn, δ). □

We will need the following two theorems: Ore’s Theorem [7]. If G is an (n, δ)-graph with δ ≥ 1 then γ(G) ≤ n/2. □ Reed’s Theorem [9]. If G is an (n, δ)-graph with δ ≥ 3 then γ(G) ≤ 3n/8. □ Proposition 2.3. For n ≥ 1

γ(n, 0) = γ_{r}(n, 0) = n

and for n ≥ 2

γ(n, 1) = γ_{r}(n, 1) = ⌊n/2⌋. □

Proof. The case δ = 0 is trivial and the case δ = 1 is immediate from Ore’s Theorem. □ Proposition 2.4. For n ≥ 3,

γ(n, 2) = γ_{r}(n, 2) = \{ \begin{matrix}⌊n/2⌋ − 1, & if n ≡ 2 (mod 4) \\ ⌊n/2⌋, & otherwise. \end{matrix}

Proof. From Ore’s Theorem we have γ(n, 2) ≤ ⌊n/2⌋. Consider the four cases: (1) n = 4k, k ≥ 1.

(2) n = 4k + 1, k ≥ 1.

(3) n = 4k + 2, k ≥ 1.

(4) n = 4k + 3, k ≥ 0.

the electronic journal of combinatorics 4 (1997), #R26 5

In cases (1) and (2) ⌊n/2⌋ = 2k so in these cases it suffices to exhibit a 2-regular graph G with γ(G) = 2k. In case (1) we can take G to be the disjoint union of k 4-cycles. In case (2) we can take G to be the disjoint union of k − 1 4-cycles and one 5-cycle. In case (4) we can take G to be the union of k 4-cycles and one 3-cycle. Then γ(G) = 2k + 1 = ⌊n/2⌋.

For case (3) we first note that by [8] or [3] if a graph G has no isolated vertices and if γ(G) = n/2 then each connected component of G is either a 4-cycle or has a vertex of degree 1. Since we are interested here only in graphs with δ = 2 it follows that such a graph cannot have γ(G) = n/2 unless it has order 4k. So in case (3) we have γ(n, 2) ≤ n/2 − 1. To see that this upper bound can be attained one must only consider the disjoint union of k − 1 4-cycles and one 6-cycle. □ Proposition 2.5. If n ≥ 4 then

γ(n, 3) = γ_{r}(n, 3) = ⌊3n/8⌋.

Proof. From Reed’s Theorem γ(n, 3) ≤ 3n/8. Thus it suffices to exhibit for each n ≥ 4 an (n, 3)-graph G_{n} which is 3-regular if n is even and almost regular if n is odd such that γ(G_{n}) = ⌊3n/8⌋.

We first note that it suffices to find the graphs G_{n} for 4 ≤ n ≤ 11: For 12 ≤ n ≤ 15 we can take

G_{15} = G_{8} ∪ G_{7}, G_{14} = G_{8} ∪ G_{6}, G_{13} = G_{8} ∪ G_{5}, G_{12} = G_{8} ∪ G_{4}.

If n ≥ 16 we can write n = 8k + r where k ≥ 1 and r ∈ {8, 9, 10, 11, 12, 13, 14, 15}. Then ⌊3n/8⌋ = 3k + ⌊3r/8⌋. So if we let G_{n} be the disjoint union of k copies of G_{8} and one copy of G_{r} we have

γ(G_{n}) = kγ(G_{8}) + γ(G_{r}) = 3k + ⌊3r/8⌋ = ⌊3n/8⌋.

Moreover since G_{8} is 3-regular, G_{n} will be regular if r is even and almost regular if r is odd.

the electronic journal of combinatorics 4 (1997), #R26 6

This leaves the cases 4 ≤ n ≤ 11. It is easy to see that we may take G_{4} = K_{4}, G_{5} = K_{5} − {two disjoint edges}, G_{6} = any regular (6,3)-graph, G_{7} = any almost regular (7,3)-graph, G_{8} can be taken to be the 8-cycle with 4 diameters added, and G_{10} = G_{4} ∪ G_{6}. This leaves only G_{9} and G_{11}. See appendix B for these graphs, namely, the graphs listed there as G(9, 3, 3) and G(11, 3, 4). □

3. The cases δ = n − k for k small.

We first describe an upper bound for γ(n, δ) which is a variation of Theorem 2 in [2]. This result plays a major role in almost all of our arguments.

Proposition 3.1. Let G be an (n, δ)-graph containing a set S of s vertices which covers at least λ vertices. Define the sequence g_{s}, g_{s+1}, ⋯, g_{n−δ} by g_{s} = n − λ and

g_{t+1} = ⌊g_{t} (1 − \frac{δ + 1}{n − t})⌋ = g_{t} − ⌈\frac{g_{t}(δ + 1)}{n − t}⌉ , t ≥ s.

Then for any t, s ≤ t ≤ n − δ, there is a set of t vertices that covers at least n − g_{t} vertices. Thus if we set

M(n, δ, λ, s) = min{ t | g_{t} = 0 }

we have

γ(G) ≤ M(n, δ, λ, s).

In particular,

γ(n, δ) ≤ M(n, δ, δ + 1, 1)

and if nδ is odd,

γ(n, δ) ≤ M(n, δ, δ + 2, 1).

Proof. Starting with the set S = {v_{1}, v_{2}, ⋯, v_{s}} we select successively and greedily the elements v_{s+1}, v_{s+2}, ⋯, v_{t}. Let u_{t}, t ≥ s, be the number of vertices left uncovered after the vertices v_{1}, v_{2}, ⋯, v_{t} have been chosen. It clearly suffices to

the electronic journal of combinatorics 4 (1997), #R26 7

prove that u_{t} ≤ g_{t} for t ≥ s. We prove this by induction on t. If t = s then since S covers at least λ vertices u_{s} ≤ n − λ = g_{s}.

Assume that u_{t} ≤ g_{t} holds for some t ≥ s. Let

U_{t} = {x_{1}, x_{2}, ⋯, x_{u_{t}}}

be the set of vertices not covered by v_{1}, v_{2}, ⋯, v_{t} and let

V − {v_{1}, ⋯, v_{t}} = {y_{1}, y_{2}, ⋯, y_{n−t}}.

Now define the u_{t} × (n − t) matrix M whose (i, j)-th entry is given by

M_{i,j} = \{ \begin{matrix}1, & if x_{i} covers y_{j} \\ 0, & otherwise. \end{matrix}

Since none of the x_{i}’s are covered by any of the vertices v_{1}, v_{2}, ⋯, v_{t} chosen so far and deg(x_{i}) ≥ δ there are at least δ + 1 ones in each row of M. This gives at least u_{t}(δ + 1) ones in the entire matrix. Since there are n − t columns at least one column must contain at least

N = ⌈\frac{u_{t}(δ + 1)}{n − t}⌉

ones. Say it is the j-th column. This means that y_{j} covers at least N of the x_{i}’s. So if we select v_{t+1} to cover the maximum number N_{max} of the x_{i}’s we have N ≤ N_{max} and the number of vertices now left uncovered is

u_{t+1} = u_{t} − N_{max}

≤ u_{t} − N

= u_{t} − ⌈\frac{u_{t}(δ + 1)}{n − t}⌉

= u_{t} + ⌊−\frac{u_{t}(δ + 1)}{n − t}⌋

= ⌊u_{t} (1 − \frac{δ + 1}{n − t})⌋

≤ ⌊g_{t} (1 − \frac{δ + 1}{n − t})⌋

= g_{t+1}.

This completes the proof. □

the electronic journal of combinatorics 4 (1997), #R26 8

Proposition 3.2.

(1) γ(n, n − 1) = γ_{r}(n, n − 1) = 1 for any n ≥ 1.

(2) γ(n, n − 2) = γ_{r}(n, n − 2) = 1 for odd n ≥ 2.

(3) γ(n, n − 2) = γ_{r}(n, n − 2) = 2 for even n ≥ 2.

Proof. For each of the cases (1) and (2) there is a vertex of degree n − 1 which by itself forms a dominating set. For case (3) any regular graph with δ = n − 2 clearly has domination number 2. □ Lemma 3.3. Let n ≥ 2 and let G be an (n, δ)-graph with a vertex of degree Δ. Then γ(G) ≤ 2 if

(3.1)  (n − Δ − 1)(n − δ − 2) < n − 1

. Proof. By Proposition 3.1 γ(G) ≤ M(n, δ, Δ+1, 1) and M(n, δ, Δ+1, 1) = 2 if and only if g_{2} = 0. Now g_{1} = n − Δ − 1 and

g_{2} = ⌊g_{1} (1 − \frac{δ + 1}{n − 1})⌋ .

So g_{2} = 0 if and only if

(n − Δ − 1) (1 − \frac{δ + 1}{n − 1}) < 1

which is equivalent to (3.1). □ Proposition 3.4. Let 3 ≤ k ≤ n − 1.

(1) If (k − 1)(k − 2) + 1 < n then

γ(n, n − k) = γ_{r}(n, n − k) = 2.

(2) If n is odd, k is even and (k − 2)^{2} + 1 < n then

γ(n, n − k) = γ_{r}(n, n − k) = 2

the electronic journal of combinatorics 4 (1997), #R26 9

Proof. If k ≥ 3 then γ(n, n − k) ≠ 1 since a regular or almost regular graph with δ = n − k has vertices of degree at most n − k + 1 so a single vertex cannot cover all n vertices. Hence whenever γ(n, n − k) ≤ 2 we have γ(n, n − k) = γ_{r}(n, n − k) = 2. By Lemma 3.3 γ(n, n − k) ≤ 2 if (k − 1)(k − 2) + 1 < n. This proves (1). To prove (2) we observe that if n is odd and k is even then δ = n − k is odd and so any (n, δ)-graph has a vertex of degree at least δ+1 so we can take Δ = δ+1 = n−k+1 in (3.1) and we obtain (2). □

Corollary 3.5.

(1) γ(n, n − 3) = γ_{r}(n, n − 3) = 2 if n > 3.

(2) γ(n, n − 4) = γ_{r}(n, n − 4) = 2 if n ≥ 7.

(3) γ(n, n − 5) = γ_{r}(n, n − 5) = 2 if n > 13.

(4) γ(n, n − 6) = γ_{r}(n, n − 6) = 2 if n ≥ 21 or n = 19.

(5) γ(n, n − 7) = γ_{r}(n, n − 7) = 2 if n > 31. □

4. γ(n, δ) for n ≤ 16.

In Table 1 we give a list of values (or bounds) for γ(n, δ) when n ≤ 16. In this section we justify the entries of this table. See Table 3 in Appendix A for a summary of how entries in Table 1 are obtained. From Propositions 2.3, 2.4, 2.5, 3.2 and Corollary 3.5 we obtain immediately the exact values of γ(n, δ) for all values of n and δ for n ≤ 16 except for the following 33 cases:

(1) n = 9, δ = 4.

(2) n = 10, δ = 4, 5.

(3) n = 11, δ = 4, 5, 6.

(4) n = 12, δ = 4, 5, 6, 7.

(5) n = 13, δ = 4, 5, 6, 7, 8.

(6) n = 14, δ = 4, 5, 6, 7, 8.

(7) n = 15, δ = 4, 5, 6, 7, 8, 9.

(8) n = 16, δ = 4, 5, 6, 7, 8, 9, 10.

the electronic journal of combinatorics 4 (1997), #R26 10

The number of unknown γ(n, δ) can be reduced further by using the upper bounds given in Proposition 3.1 (taking s = 1) and Reed’s Theorem. See Table 2 for upper bounds computed using Proposition 3.1. Let Ub(n, δ) denote M(n, δ, δ +1, 1) if nδ is even or M(n, δ, δ + 2, 1) if nδ is odd. If the entry in the (n, δ)-th cell of Table 2 is a single number then that number is Ub(n, δ) and is, in fact, equal to γ(n, δ). So only an example suffices to establish γ(n, δ) in these cases. Tight lower bounds are given by the graphs G(n, δ, γ) in Appendix B. Each graph G(n, δ, γ) listed in Appendix B is an (n, δ)-graph with domination number γ. These graphs are regular if nδ is even and almost regular otherwise. After applying these results we have only the following 15 remaining cases:

(1) n = 10, δ = 5.

(2) n = 11, δ = 4.

(3) n = 12, δ = 7.

(4) n = 13, δ = 5, 8.

(5) n = 14, δ = 4, 6.

(6) n = 15, δ = 5, 6, 9.

(7) n = 16, δ = 4, 5, 7, 9, 10.

As indicated in Table 3 (in Appendix A) all but 6 of these cases are settled by one of the following propositions and/or the use of an exhaustive search using Brendan McKay’s program makeg augmented with a subroutine to compute domination numbers. For example we use Propostion 4.1 below to reduce the determination of γ(10, 5) to the determination of γ_{r}(10, 5). Then we search through all 5-regular graphs of order 10 to find that γ_{r}(10, 5) = 2.

Table 2. Upper bounds given by Proposition 3.1 for 5 ≤ n ≤ 16

n ⧹ δ  4  5  6  7  8  9  10 11 12 13 14 15
5  1
6  2  1
7  2  1  1
8  2  2  2  1
9  3  2  2  1  1
10  3  2,3,7  2  2  2  1
11 3,4,5  3  3  2  2  1  1
12  4  3  3  2,3,8  2  2  2 1
13 4,5,6 3,4,7  3  3  2,3,9 2  2 1 1
14 4,5,7  4  3,4,7  3  3  2  2 2 2 1
15  5  4,5,8 3-4*  3  3  2-3* 2 2 2 1 1
16 5,6,5 4-5*  4  3-4*  3  2-3* 2-3* 2 2 2 2 1

An entry of the form a, a+1, λ indicates that γ(n, δ) = a and Ub(n, δ) = a + 1. λ is the least postive integer for which M(n, δ, λ + 1, 1) = a. Thus in these cases one obtains a tight upper bound by assuming the existence of a vertex of degree λ. In cells containing x-y∗ the value of γ(n, δ) is unknown, but our current best upper bound is given by Ub(n, δ) = y and x is our current best lower bound.

Several times below we need the following trivial result.

Lemma 4.0. Let F be a set of two element subsets of a four element set X. If the

following two conditions hold

(1) A ∩ B ≠ ∅ for all A, B ∈ F, and

(2) ⋃_{A∈F} A = X,

then ⋂_{A∈F} A ≠ ∅ □

Proposition 4.1. 2 ≤ γ_{r}(10, 5) = γ(10, 5) ≤ 3.

Proof. From Proposition 3.1 (see Table 2) we obtain γ(10, 5) ≤ 3 so it suffices to

show that if G = (V, E) is a (10,5)-graph that is not regular then γ(G) ≤ 2. If

Δ ≥ 7 then by Lemma 3.3 (or Table 2), γ(G) ≤ 2. So suppose that Δ = 6. Let x be

a vertex of degree 6. Then V is the disjoint union of N[x], the closed neighborhood

the electronic journal of combinatorics 4 (1997), #R26 12

of x, and the 3-set A = {a, b, c}. If the induced graph H = ⟨A⟩ has 2 edges then it can be dominated by a single vertex. So we can assume that H has at most one edge. Thus H has at least one isolated vertex, say, c. This means that c is adjacent to at least 5 vertices in the open neighborhood N(x) of x and each of the remaining two vertices a and b are adjacent to at least 4 vertices of N(x). It follows that there is at least one vertex y in N(x) that is adjacent to all three vertices in A. Hence {x, y} is a dominating set for G. □

Proposition 4.2. 3 ≤ γ_{r}(11, 4) = γ(11, 4) ≤ 4

Proof. By Proposition 3.1 γ(11, 4) ≤ 4. By Lemma 2.1 and the above

γ_{r}(11, 4) ≥ γ_{r}(6, 4) + γ_{r}(5, 4) = 3.

So it suffices to show that if G an (11,4) graph that is not regular then γ(G) ≤ 3. But it is immediate from Proposition 3.1 that if Δ ≥ 5 then γ ≤ 3. □

Proposition 4.3. 2 ≤ γ_{r}(12, 7) = γ(12, 7) ≤ 3

Proof. Any regular (12,7)-graph has 2 ≤ γ. By Proposition 3.1 if G is a (12,7)-graph with γ(G) ≤ 3 and Δ ≥ 8, then γ(G) ≤ 2, and the proposition follows. □

Proposition 4.4. γ_{r}(13, 5) = γ(13, 5) = 3.

Proof. By Appendix B there is an almost regular (13,5)-graph with domination number 3 so 3 ≤ γ_{r}(13, 5) ≤ γ(13, 5). It therefore suffices to show that γ(13, 5) ≤ 3. If G = (V, E) is a (13,5)-graph with maximum degree Δ ≥ 7 then from Proposition 3.1 we have γ(G) ≤ 3. Now if Δ ≤ 6 then since nδ is odd G will always a vertex x of degree 6. Thus V is a disjoint union of the closed neighborhood N[x] of x and a set A of cardinality 6. Consider the 6 × 12 matrix M whose rows are indexed by the elements of A and the columns are indexed by the elements of V − {x}. If a ∈ A is adjacent to or equal to y ∈ V − {x} let M_{a,y} = 1. Otherwise, let M_{a,y} = 0. Now each row of M has at least 6 ones, so M has in all at least 36 ones.

the electronic journal of combinatorics 4 (1997), #R26 13

If there is a column with 4 ones this means there is a vertex y ∈ V − {x} that covers all but two vertices, say, z, w in A. If the sets N[z], N[w] are disjoint their union contains all but one vertex t. Then {z, w, t} is a dominating set and we are done. But if v ∈ N[z] ∩ N[w], then v dominates both z and w so {x, y, v} is a dominating set.

We are left with the case where each column of M contains at most three ones. This implies that each column contains exactly three ones. Hence each vertex in the subgraph H = ⟨A⟩ has degree exactly 2. Hence H is a (6,2)-graph and by Proposition 2.4 can be dominated by two vertices. Hence G can be dominated by x together with these two vertices and we are done. □

Proposition 4.5. 2 ≤ γ_{r}(13, 8) = γ(13, 8) ≤ 3.

Proof. Any regular (13,8)-graph G has domination number at least 2. By Lemma 3.3 if G has a vertex of degree greater than 8 then γ(G) ≤ 2. □

Proposition 4.6. γ_{r}(14, 4) = γ(14, 4) = 4.

Proof. From Appendix B there is a 4-regular graph of order 14 with domination number 4. This lower bound also follows from Lemma 2.1 and the fact that γ(7, 4) = γ_{r}(7, 4) = 2 by Corollary 3.5. Thus it suffices to show that if G = (V, E) is a (14,4)- graph then γ(G) ≤ 4. If there is a vertex of degree 7 we obtain γ(G) ≤ 4 from Proposition 3.1. Hence we may assume that Δ is at most 6.

We consider two cases:

(1) There are vertices a and b such that |N[a] ∪ N[b]| ≥ 10.

(2) For all vertices a and b we have |N[a] ∪ N[b]| ≤ 9. In case (1) if |N[a] ∪ N[b]| ≥ 11 we get γ(G) ≤ 4 immediately from Proposition 3.1 with s = 2 and λ = 11. Hence can assume that |N[a] ∪ N[b]| = 10. We let A be the set of 4 vertices not in N[a] ∪ N[b] and H = ⟨A⟩. Let

B = (N[a] ∪ N[b]) − {a, b}.

the electronic journal of combinatorics 4 (1997), #R26 14

For each vertex v ∈ B let A_{v} be the set of vertices in A that are adjacent to v. If |A_{v}| ≥ 3 for some v then v covers at least three vertices from A and then clearly γ(G) ≤ 4. Hence we may assume that |A_{v}| ≤ 2 for each v ∈ B. Note that the sum of the |A_{v}|’s is the number of edges from A to B.

If H has 2 edges then γ(H) ≤ 2 so γ(G) ≤ 4. So we may assume that H has at most one edge. We consider the two subcases:

(1a) H has no edges; and (1b) H has exactly one edge.

If (1a) holds then there are at least 4 · 4 = 16 edges from A to B. Thus, the sum of the |A_{v}|’s is at least 16. Since |A_{v}| ≤ 2 for all v ∈ B we must have |A_{v}| = 2 for all eight v in B. If A_{v_{1}} ∩ A_{v_{2}} = ∅ then A_{v_{1}} ∪ A_{v_{2}} = A and so {a, b, v_{1}, v_{2}} is a dominating set for G. So we can assume that A_{v_{1}} ∩ A_{v_{2}} ≠ ∅ for all v_{1} and v_{2}. The sets A_{v} must cover A as the vertices of A have degree at least 4 in G. Clearly the hypotheses of Lemma 4.0 hold for F = {A_{v} | v ∈ B} and hence the A_{v}’s contain a common element. But this common element would be a vertex of degree 8, contrary to the assumption that Δ ≤ 6. This settles case (1a).

Assume that (1b) holds. Let A = {x, y, z, w} and assume that {z, w} is the single edge in H. In this case there are at least 14 edges from A to B and there must be at least 6 of the A_{v}’s that have cardinality 2. If there were more than 6 the argument for case (1a) repeated would show the existence of a vertex of degree greater than 6, a situation already handled. Thus we may assume that there are exactly 6 vertices v, in B such that |A_{v}| = 2. If for some i, A_{v_{i}} = {x, y} then {a, b, v_{i}, z} is a domination set for G. We show this must happen. If not, since both x and y have degree at least 4 in G but degree 0 in H we can assume that A_{v_{i}} contains x for i = 1, 2, 3, 4 and that A_{v_{i}} contains y for i = 5, 6, 7, 8. This means that the two A_{v}’s that have one element must contain either an x or a y. It follows that there are at least three of the two element A_{v}’s that contain z and at least three, that contain w. So it is clear that we cannot avoid having either two A_{v}’s of

the electronic journal of combinatorics 4 (1997), #R26 15

the form {x, z} and {y, w} or, of the form {x, w} and {y, z}. But this contradicts our assumption that the two element A_{v}’s are never disjoint. This completes the proof in case (1b) and hence the proof of case (1).

Assume that case (2) holds. Note that if G is not regular then it contains a vertex of degree at least 5 and by Proposition 3.1 there will be two vertices that cover at least 10 vertices which puts us back in case (1). Thus we can assume that G is 4-regular. Note that this implies that N[a] ∩ N[b] ≠ ∅ for all vertices a and b. Hence any two vertices can be covered by a single vertex. Thus if we are able to show that we can cover 12 vertices with 3 vertices we will know that γ(G) ≤ 4. By Proposition 3.1 there are two vertices a and b such that N[a] ∪ N[b] = 9. Let

B = (N[a] ∪ N[b]) − {a, b}

and let

A = V − (N[a] ∪ N[b]).

Now again let H = ⟨A⟩. If H contains a vertex x of degree 2 we can cover 12 vertices with the a, b and x and we are done. So we can assume that H has only vertices of degree 1 and hence H has at most 2 edges. It follows that there must be at least 16 edges with one end in A and the other end in B. Since |A| = 5 and |B| = 7 there must be at least one vertex x ∈ B that is incident with at least 3 vertices in A. Then a, b and x cover all but 2 vertices in A and as before we are done. □ Lemma 4.7. A graph G = (V, E) with |V | = 7, |E| ≥ 10, and Δ ≤ 3 satisfies γ(G) ≤ 2. Proof. The graph G = (V, E) must have six vertices of degree 3 and a single vertex of degree 2. Let v be a vertex of degree 3 which is adjacent to a vertex of degree 2. Let A denote the set of three vertices not adjacent to v. If ⟨A⟩ has two or more edges, then clearly G can be dominated by v together with a vertex of degree 2 taken from ⟨A⟩. So we may assume that ⟨A⟩ has at most one edge. The sum of the

the electronic journal of combinatorics 4 (1997), #R26 16

degrees (in G) of the vertices of A is 9 since the single vertex of degree 2 is not in A. Since ⟨A⟩ has at most one edge, there are at least 7 = 9 − 2 edges between N(v) and A. Hence at least one vertex, say x, in N(v) must be incident with 3 of these edges. It follows that {x, v} is a dominating set for G. □

The restriction that Δ ≤ 3 in the preceding lemma is essential. A graph with γ = 3 can be constructed meeting the other hypotheses even if we assume no isolated vertices. Begin with the tetrahedron K_{4}. Add an additional vertex connecting it to any two vertices of the tetrahedron. Finally, add two additional vertices, connecting each to one of the remaining two vertices of the tetrahedron. This graph has 10 edges and 7 vertices, but has maximum degree 4 and minimum degree 1. The graphs described by the lemma had maximum degree 3 and minimum degree 2. There is also a graph with 7 vertices, 10 edges, minimum degree 2, maximum degree 4 with domination number 3. Proposition 4.8. γ_{r}(14, 6) = γ(14, 6) = 3. Proof. By Appendix B there is a regular (14, 6)-graph whose domination number is 3. That γ_{r}(14, 6) = γ(14, 6) follows from Proposition 3.1. It remains to prove that γ_{r}(14, 6) ≤ 3.

Let G = (V, E) be a regular (14, 6)-graph. Since every closed neighborhood contains 7 vertices, γ(G) = 2 if there are disjoint closed neighborhoods in G. Thus we can assume that any two closed neighborhoods N[x] and N[y] intersect in at least one point. This implies that any two vertices can be covered by a single vertex. So if we can cover 12 vertices with just 2 vertices we will be done.

Let v ∈ V and set A = V − N[v]. If γ(⟨A⟩) ≤ 2 we are clearly done. If ⟨A⟩ has a vertex of degree at least 4 it covers 5 vertices in addition to the 7 covered by v and we are done. So we can assume that the maximum degree of a vertex in ⟨A⟩ is 3. If there are at least 10 edges in ⟨A⟩ we are done by Lemma 4.7. Thus we may assume that ⟨A⟩ has at most 9 edges. An endpoint of an edge in G is either in A or N(v). Since ⟨A⟩ has at most 9 edges and G is 6-regular there are at least

the electronic journal of combinatorics 4 (1997), #R26 17

24 = |A| · 6 − 2 · 9 edges from A to N(v). If some vertex in N(v) covers 5 or more of the vertices in A we are done. Thus each of the 6 vertices in N(v) is incident with at most 4 of the vertices in A. This implies that there are exactly 24 edges between A and N(v) and that each x ∈ N(v) is incident to v and to exactly four vertices in A. It follows that ⟨N(v)⟩ is a 1-regular graph.

Thus we can assume that for every vertex v ∈ V the graph ⟨N(v)⟩ is 1-regular. But we shall see that this is impossible: Let v ∈ V and let x, y ∈ N(v) be chosen such that x ∼ y. It is clear that

N[v] ∩ N[x] ∩ N[y] = N[v] ∩ N[x] = N[v] ∩ N[y] = {v, x, y}

as x and y are adjacent only to each other in ⟨N(v)⟩. Also we have

N[x] ∩ N[y] = {v, x, y}.

For suppose, to the contrary, that w ∈ N[x] ∩ N[y] and w ∉ {v, x, y}. Then y ∈ N(x) is adjacent to both v, w ∈ N(x) which contradicts the assumption that ⟨N(x)⟩ is 1-regular. But then we have

|N[v] ∪ N[x] ∪ N[y]| =
|N[v]| + |N[x]| + |N[y]|
− |N[v] ∩ N[x]| − |N[v] ∩ N[y]| − |N[x] ∩ N[y]|
+ |N[v] ∩ N[x] ∩ N[y]|
= 7 + 7 + 7 − 3 − 3 − 3 + 3 = 15,

which cannot be since there are only 14 vertices in G. □ Proposition 4.9. γ(15, 5) = γ_{r}(15, 5) = 4. Proof. The almost regular graph G(15, 5, 4) given in Appendix B has domination number 4, so it suffices to prove that γ(15, 5) ≤ 4. Let G = (V, E) be a (15,5)- graph. If G has a vertex of at least degree at least 8 then γ(G) ≤ 4 by Proposition

the electronic journal of combinatorics 4 (1997), #R26 18

3.1. Since the minimum degree and the order are odd, there must be a vertex, say, x of degree at least 6. Again by Proposition 3.1 there is a vertex y such that |N[x] ∪ N[y]| ≥ 11. If |N[x] ∪ N[y]| ≥ 12 then Proposition 3.1 shows that γ(G) ≤ 4. So we can assume that |N[x] ∪ N[y]| = 11. Let

A = {a, b, c, d} = V − (N[x] ∪ N[y]),
B = (N[x] ∪ N[y]) − {x, y},

and H = ⟨A⟩. If H has domination number 1 or 2 we are done. So we may assume that H has at most one edge. It follows that there are at least 4 · 5 − 2 = 18 edges with one end in B and the other end in A. For each vertex v in B let A_{v} denote the vertices in A adjacent to v. If any A_{v} has three or more elements we are clearly done. So we may assume that each A_{v} has at most 2 elements. But since there are at least 18 edges joining A to B we must have |A_{v}| = 2 for each v ∈ B. Now if A_{v_{1}} ∩ A_{v_{2}} = ∅ then A_{v_{1}} ∪ A_{v_{2}} = A and so {x, y, v_{1}, v_{2}} is a dominating set for G. Thus we may assume that A_{v_{1}} ∩ A_{v_{2}} ≠ ∅ for all v_{1} and v_{2} in B. By Lemma 4.0 the A_{v}’s have an element in common. But the common element would have degree at least 9, a case we already covered. This completes the proof. □

Proposition 4.10. γ_{r}(16, 4) = γ(16, 4) = 5.

Proof. Since γ_{r}(6, 4) = 2 and γ_{r}(10, 4) = 3 there is, by Lemma 2.1, a regular graph whose domination number is 5. It remains to prove that γ(16, 4) ≤ 5.

Given a (16, 4) graph, we may assume that any two closed neighborhoods N[x] and N[y] intersect in at least one point. If they were disjoint, then Proposition 3.1 would apply with |S| = 2 and λ = 10 vertices covered.

Applying Proposition 3.1 directly with |S| = 1 and λ = 5 we obtain g_{4} = 2. Thus, 4 vertices cover all but (at most) 2 vertices. The closed neighborhoods of the remaining two vertices are not disjoint and hence they can be covered by a single vertex yielding a dominating set of at most 5 vertices. □

Proposition 4.11. 4 ≤ γ_{r}(16, 5) = γ(16, 5) ≤ 5.

Proof. A regular (16, 5)-graph whose domination number is 4 may be formed by taking the disjoint union of two regular (8, 5)-graphs whose domination numbers are 2. That γ(16, 5) ≤ 5 follows from Proposition 3.1. It will then suffice to prove that if a (16, 5)-graph G = (V, E) is not regular then γ(G) = 4.

We will show that for any x, y ∈ V, N[x] ∩ N[y] ≠ ∅. Given this, choose x ∈ V of degree at least 6 and apply Proposition 3.1 with S = {x} to conclude that g_{3} ≤ 2. This will mean that 3 vertices of G cover all but (at most) 2 vertices of G and the remaining 2 can be covered by a single vertex since their closed neighborhoods are not disjoint completing the proof.

Let x, y ∈ V and assume N[x]∩N[y] = ∅. The vertices x and y both have degree 5 or we are done by Proposition 3.1 starting with S = {x, y}. Let B = N(x)∪N(y) and let A = V − N[x] − N[y]. Clearly |A| = 4 and |B| = 10. If A can be covered by two vertices, we are done and hence < A > has at most 1 edge. Thus, there are at least 4 · 5 − 2 = 18 edges from A to B. For each v ∈ B, let A_{v} denote the set of vertices in A which are adjacent to v. If there exists v ∈ B such that |A_{v}| ≥ 3, then at most one point z of A is not covered by v and {x, y, v, z} is a dominating set. Hence we may assume that |A_{v}| ≤ 2 for each v ∈ B. Let B′ denote the set of vertices v ∈ B for which |A_{v}| = 2. Since there are at least 18 edges joining B to A we must have |B′| ≥ 8. Note that the A_{v}’s, v ∈ B′, must cover A for if a vertex in A is not adjacent to any vertex in B′ then it has degree at most 3. If there exists u, v ∈ B′ such that A_{u} and A_{v} are disjoint then {x, y, u, v} would be a dominating set. So it follows from Lemma 4.0 that the sets A_{v}, v ∈ B′, have a common vertex. This common element must be a vertex of degree at least 8. Given a vertex of degree 8, Proposition 3.1 applies to show that the domination number of G, in this case, is at most 4. □

the electronic journal of combinatorics 4 (1997), #R26 20

5. Miscellaneous Remarks

The following proposition tempts one to conjecture that γ_{r}(n, 4) = γ(n, 4) = ⌊\frac{n}{3}⌋.

Proposition 5.1. For 5 ≤ n ≤ 16,

γ_{r}(n, 4) = γ(n, 4) = ⌊\frac{n}{3}⌋

and for n ≥ 17,

⌊\frac{n}{3}⌋ ≤ γ_{r}(n, 4).

Proof. The first sentence follows from Appendix A. If n ≥ 16 then we can write n = 6ℓ + s where ℓ ≥ 1 and s ∈ {6, 7, 8, 9, 10, 11}. Now by Lemma 2.1 we have

⌊\frac{n}{3}⌋ = 2ℓ + ⌊\frac{s}{3}⌋ = ℓγ_{r}(6, 4) + γ_{r}(s, 4) ≤ γ_{r}(6ℓ + s, 4) = γ_{r}(n, 4). □

One of the authors has conjectured that γ_{r}(n, δ) = γ(n, δ) is always true. Indeed, no example to the contrary has been found in our search. Even when the value of γ(n, δ) is not known, one is sometimes able to show that γ_{r}(n, δ) = γ(n, δ), see, e.g., Proposition 4.11. The other author conjectures that γ_{r}(n, δ) = γ(n, δ) is false. The discussion following Lemma 4.7 provides an example where a more uneven distribution of degree for the vertices of a graph leads to a higher value of γ even though the number of vertices and the number of edges remains the same.

Finally we remark that if graphs are assumed to be connected at least in the cases δ = 1 or δ = 2 different results may be expected. See, for example, [5] where it is proved that with a few exceptions the domination number of a connected (n, 2)-graph is at most 2n/5.

Acknowledgement. The authors are grateful to David Fisher, Teresa Haynes, Bill McCuaig, Boris Shekhtman and Stephen Suen for useful discussions and/or help with references. Special thanks to Brendan McKay for the use of his program makeg.

References

1. I. Anderson, Combinatorics of Finite Sets, Clarendon Press, Oxford,, New York, 1987..

2. W. E. Clark, D. Fisher, B.Shekhtman and S. Suen, Upper bounds for the domination number of a graph, preprint.

3. J. F. Fink, M. S. Jacobson, L. K. Kinch and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985), 287–293..

4. T. W. Haynes, Domination in graphs: a brief overview, preprint.

5. W. McCuaig and B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989), 749-762.

6. B. D. McKay, Isomorph-free exhaustive generation, preprint.

7. O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ. 38, American Mathematical Society, Providence, 1962..

8. C. Payan and N. H. Xuong, Domination–balanced graphs, J. Graph Theory 6 (1982), 23–32..

9. B. Reed, Paths, stars, and the number three, Combin. Probab. and Comput. 5 (1996), 277–

Appendix A

Table 3. Derivation of γ(n, δ) for n ≤ 16, 0 ≤ δ ≤ n − 1.
n ⧹ δ 0 1 2 3 4  5  6  7  8  9 10 11 12 13 14 15
1  2.3
2  2.3 2.3
3  2.3 2.3 2.4
4  2.3 2.3 2.4 3.1
5  2.3 2.3 2.4 3.1 3.1
6  2.3 2.3 2.4 3.1 3.1 3.1
7  2.3 2.3 2.4 3.1 3.1 3.1 3.1
8  2.3 2.3 2.4 R 3.1 3.1 3.1 3.1
9  2.3 2.3 2.4 R 3.1a 3.1 3.1 3.1 3.1
10  2.3 2.3 2.4 R 3.1a 4.1c 3.1 3.1 3.1 3.1
11  2.3 2.3 2.4 R 4.2c 3.1a 3.1a 3.1 3.1 3.1 3.1
12  2.3 2.3 2.4 R 3.1b 3.1a 3.1a 4.3c 3.1 3.1 3.1 3.1
13  2.3 2.3 2.4 R Rd 4.4 3.1a 3.1a 4.5c 3.1 3.1 3.1 3.1
14  2.3 2.3 2.4 R 4.6 3.1a 4.8e 3.1a 3.1a 3.1 3.1 3.1 3.1 3.1
15  2.3 2.3 2.4 R 3.1f 4.9 3.1a 3.1a 3.1a 3.1 3.1 3.1 3.1 3.1 3.1
16  2.3 2.3 2.4 R 4.10 3.1b 3.1b 3.1a 3.1a 3.1 3.1 3.1 3.1 3.1 3.1 3.1

The number in the (n, δ)-th cell is the number of the proposition which justifies the corresponding value in Table 1. The letter code is as follows:

a With lower bound from Appendix B graph G(n, δ, γ) b Also used Lemma 2.1 with γ(n, δ) = 2 ∗ γ(n/2, δ) c Also required computer search d Also used Lemma 2.1 with γ(7, 4) + γ(6, 4) = 4 e Confirmed by computer search using 11 days of cpu time f Also used Lemma 2.1 with γ(9, 4) + γ(6, 4) = 5 R Reed’s Theorem

Appendix B

Each graph G(n, δ, γ) listed below is an (n, δ)-graph with domination number γ. All graphs are either regular or almost regular. The vertices are numbered 0, 1, …, n − 1 and the i-th row represents the neighbors of the vertex in the first entry of that row. These graphs were found by Brendan McKay’s program makeg augmented by a program to check domination numbers or by ad hoc construction in two case.

G(9, 3, 3) = [ \begin{matrix}0 & 1 & 2 & 4 \\ 1 & 0 & 2 & 3 \\ 2 & 0 & 1 & 3 \\ 3 & 1 & 2 & 4 \\ 4 & 0 & 3 & 5 & 8 \\ 5 & 4 & 6 & 7 \\ 6 & 5 & 7 & 8 \\ 7 & 5 & 6 & 8 \\ 8 & 4 & 6 & 7 \end{matrix} ] G(11, 3, 4) = [ \begin{matrix}0 & 1 & 2 & 5 \\ 1 & 0 & 2 & 4 \\ 2 & 0 & 1 & 3 \\ 3 & 2 & 4 & 7 \\ 4 & 1 & 3 & 5 & 10 \\ 5 & 0 & 4 & 6 \\ 6 & 5 & 8 & 9 \\ 7 & 3 & 8 & 9 \\ 8 & 6 & 7 & 10 \\ 9 & 6 & 7 & 10 \\ 10 & 4 & 8 & 9 \end{matrix} ]

G(9, 4, 3) = [ \begin{matrix}0 & 1 & 2 & 5 & 8 \\ 1 & 0 & 2 & 4 & 7 \\ 2 & 0 & 1 & 3 & 6 \\ 3 & 2 & 4 & 5 & 8 \\ 4 & 1 & 3 & 5 & 7 \\ 5 & 0 & 3 & 4 & 6 \\ 6 & 2 & 5 & 7 & 8 \\ 7 & 1 & 4 & 6 & 8 \\ 8 & 0 & 3 & 6 & 7 \end{matrix} ] G(10, 4, 3) = [ \begin{matrix}0 & 1 & 2 & 3 & 9 \\ 1 & 0 & 2 & 3 & 8 \\ 2 & 0 & 1 & 3 & 5 \\ 3 & 0 & 1 & 2 & 4 \\ 4 & 3 & 5 & 6 & 7 \\ 5 & 2 & 4 & 6 & 7 \\ 6 & 4 & 5 & 8 & 9 \\ 7 & 4 & 5 & 8 & 9 \\ 8 & 1 & 6 & 7 & 9 \\ 9 & 0 & 6 & 7 & 8 \end{matrix} ]

G(11, 5, 3) = [ \begin{matrix}0 & 1 & 2 & 3 & 5 & 9 \\ 1 & 0 & 2 & 3 & 5 & 8 \\ 2 & 0 & 1 & 3 & 4 & 7 \\ 3 & 0 & 1 & 2 & 4 & 7 \\ 4 & 2 & 3 & 5 & 6 & 8 & 10 \\ 5 & 0 & 1 & 4 & 6 & 10 \\ 6 & 4 & 5 & 7 & 8 & 9 \\ 7 & 2 & 3 & 6 & 9 & 10 \\ 8 & 1 & 4 & 6 & 9 & 10 \\ 9 & 0 & 6 & 7 & 8 & 10 \\ 10 & 4 & 5 & 7 & 8 & 9 \end{matrix} ] G(11, 6, 3) = [ \begin{matrix}0 & 1 & 2 & 4 & 7 & 9 & 10 \\ 1 & 0 & 2 & 3 & 5 & 7 & 10 \\ 2 & 0 & 1 & 3 & 4 & 6 & 8 \\ 3 & 1 & 2 & 4 & 5 & 8 & 9 \\ 4 & 0 & 2 & 3 & 5 & 6 & 9 \\ 5 & 1 & 3 & 4 & 6 & 7 & 10 \\ 6 & 2 & 4 & 5 & 7 & 8 & 10 \\ 7 & 0 & 1 & 5 & 6 & 8 & 9 \\ 8 & 2 & 3 & 6 & 7 & 9 & 10 \\ 9 & 0 & 3 & 4 & 7 & 8 & 10 \\ 10 & 0 & 1 & 5 & 6 & 8 & 9 \end{matrix} ]

G(12, 5, 3) = [ \begin{matrix}0 & 1 & 2 & 3 & 9 & 10 \\ 1 & 0 & 2 & 3 & 4 & 8 \\ 2 & 0 & 1 & 3 & 4 & 5 \\ 3 & 0 & 1 & 2 & 4 & 5 \\ 4 & 1 & 2 & 3 & 5 & 11 \\ 5 & 2 & 3 & 4 & 6 & 7 \\ 6 & 5 & 7 & 8 & 10 & 11 \\ 7 & 5 & 6 & 8 & 9 & 11 \\ 8 & 1 & 6 & 7 & 9 & 10 \\ 9 & 0 & 7 & 8 & 10 & 11 \\ 10 & 0 & 6 & 8 & 9 & 11 \\ 11 & 4 & 6 & 7 & 9 & 10 \end{matrix} ] G(12, 6, 3) = [ \begin{matrix}0 & 1 & 2 & 3 & 5 & 7 & 11 \\ 1 & 0 & 2 & 3 & 4 & 8 & 10 \\ 2 & 0 & 1 & 3 & 4 & 7 & 11 \\ 3 & 0 & 1 & 2 & 4 & 6 & 9 \\ 4 & 1 & 2 & 3 & 5 & 6 & 10 \\ 5 & 0 & 4 & 6 & 7 & 10 & 11 \\ 6 & 3 & 4 & 5 & 7 & 8 & 9 \\ 7 & 0 & 2 & 5 & 6 & 8 & 9 \\ 8 & 1 & 6 & 7 & 9 & 10 & 11 \\ 9 & 3 & 6 & 7 & 8 & 10 & 11 \\ 10 & 1 & 4 & 5 & 8 & 9 & 11 \\ 11 & 0 & 2 & 5 & 8 & 9 & 10 \end{matrix} ]

G(13, 6, 3) = [ \begin{matrix}0 & 6 & 7 & 8 & 9 & 10 & 11 \\ 1 & 6 & 7 & 8 & 9 & 10 & 11 \\ 2 & 6 & 8 & 9 & 10 & 11 & 12 \\ 3 & 6 & 8 & 9 & 10 & 11 & 12 \\ 4 & 7 & 8 & 9 & 10 & 11 & 12 \\ 5 & 7 & 8 & 9 & 10 & 11 & 12 \\ 6 & 0 & 1 & 2 & 3 & 7 & 12 \\ 7 & 0 & 1 & 4 & 5 & 6 & 12 \\ 8 & 0 & 1 & 2 & 3 & 4 & 5 \\ 9 & 0 & 1 & 2 & 3 & 4 & 5 \\ 10 & 0 & 1 & 2 & 3 & 4 & 5 \\ 11 & 0 & 1 & 2 & 3 & 4 & 5 \\ 12 & 2 & 3 & 4 & 5 & 6 & 7 \end{matrix} ] G(13, 5, 3) = [ \begin{matrix}0 & 1 & 2 & 3 & 4 & 6 \\ 1 & 0 & 2 & 3 & 4 & 5 \\ 2 & 0 & 1 & 3 & 4 & 5 \\ 3 & 0 & 1 & 2 & 4 & 5 \\ 4 & 0 & 1 & 2 & 3 & 5 \\ 5 & 1 & 2 & 3 & 4 & 6 \\ 6 & 0 & 5 & 7 & 8 & 9 & 12 \\ 7 & 6 & 8 & 10 & 11 & 12 \\ 8 & 6 & 7 & 9 & 10 & 11 \\ 9 & 6 & 8 & 10 & 11 & 12 \\ 10 & 7 & 8 & 9 & 11 & 12 \\ 11 & 7 & 8 & 9 & 10 & 12 \\ 12 & 6 & 7 & 9 & 10 & 11 \end{matrix} ]

G(13, 4, 4) = [ \begin{matrix}0 & 1 & 2 & 3 & 12 \\ 1 & 0 & 2 & 3 & 10 \\ 2 & 0 & 1 & 3 & 5 \\ 3 & 0 & 1 & 2 & 4 \\ 4 & 3 & 6 & 7 & 11 \\ 5 & 2 & 6 & 7 & 11 \\ 6 & 4 & 5 & 8 & 9 \\ 7 & 4 & 5 & 8 & 9 \\ 8 & 6 & 7 & 10 & 12 \\ 9 & 6 & 7 & 10 & 12 \\ 10 & 1 & 8 & 9 & 11 \\ 11 & 4 & 5 & 10 & 12 \\ 12 & 0 & 8 & 9 & 11 \end{matrix} ] G(13, 7, 3) = [ \begin{matrix}0 & 1 & 2 & 3 & 6 & 7 & 8 & 12 \\ 1 & 0 & 2 & 3 & 4 & 6 & 10 & 12 \\ 2 & 0 & 1 & 3 & 4 & 5 & 10 & 11 \\ 3 & 0 & 1 & 2 & 4 & 5 & 8 & 9 \\ 4 & 1 & 2 & 3 & 5 & 6 & 7 & 9 \\ 5 & 2 & 3 & 4 & 6 & 7 & 11 & 12 \\ 6 & 0 & 1 & 4 & 5 & 7 & 8 & 11 & 12 \\ 7 & 0 & 4 & 5 & 6 & 8 & 9 & 10 \\ 8 & 0 & 3 & 6 & 7 & 9 & 10 & 11 \\ 9 & 3 & 4 & 7 & 8 & 10 & 11 & 12 \\ 10 & 1 & 2 & 7 & 8 & 9 & 11 & 12 \\ 11 & 2 & 5 & 6 & 8 & 9 & 10 & 12 \\ 12 & 0 & 1 & 5 & 6 & 9 & 10 & 11 \end{matrix} ]

G(14, 6, 3) = [ \begin{matrix}0 & 6 & 7 & 8 & 9 & 10 & 11 \\ 1 & 6 & 7 & 9 & 10 & 12 & 13 \\ 2 & 7 & 8 & 9 & 10 & 11 & 12 \\ 3 & 7 & 9 & 10 & 11 & 12 & 13 \\ 4 & 8 & 9 & 10 & 11 & 12 & 13 \\ 5 & 8 & 9 & 10 & 11 & 12 & 13 \\ 6 & 0 & 1 & 8 & 11 & 12 & 13 \\ 7 & 0 & 1 & 2 & 3 & 8 & 13 \\ 8 & 0 & 2 & 4 & 5 & 6 & 7 \\ 9 & 0 & 1 & 2 & 3 & 4 & 5 \\ 10 & 0 & 1 & 2 & 3 & 4 & 5 \\ 11 & 0 & 2 & 3 & 4 & 5 & 6 \\ 12 & 1 & 2 & 3 & 4 & 5 & 6 \\ 13 & 1 & 3 & 4 & 5 & 6 & 7 \end{matrix} ] G(14, 5, 4) = [ \begin{matrix}0 & 5 & 7 & 8 & 9 & 13 \\ 1 & 6 & 7 & 8 & 10 & 11 \\ 2 & 6 & 7 & 9 & 10 & 11 \\ 3 & 9 & 10 & 11 & 12 & 13 \\ 4 & 9 & 10 & 11 & 12 & 13 \\ 5 & 0 & 8 & 10 & 11 & 12 \\ 6 & 1 & 2 & 8 & 12 & 13 \\ 7 & 0 & 1 & 2 & 12 & 13 \\ 8 & 0 & 1 & 5 & 6 & 9 \\ 9 & 0 & 2 & 3 & 4 & 8 \\ 10 & 1 & 2 & 3 & 4 & 5 \\ 11 & 1 & 2 & 3 & 4 & 5 \\ 12 & 3 & 4 & 5 & 6 & 7 \\ 13 & 0 & 3 & 4 & 6 & 7 \end{matrix} ]

G(14, 4, 4) = [ \begin{matrix}0 & 7 & 8 & 9 & 10 \\ 1 & 7 & 8 & 9 & 11 \\ 2 & 7 & 8 & 12 & 13 \\ 3 & 7 & 8 & 12 & 13 \\ 4 & 9 & 10 & 11 & 12 \\ 5 & 9 & 10 & 11 & 13 \\ 6 & 10 & 11 & 12 & 13 \\ 7 & 0 & 1 & 2 & 3 \\ 8 & 0 & 1 & 2 & 3 \\ 9 & 0 & 1 & 4 & 5 \\ 10 & 0 & 4 & 5 & 6 \\ 11 & 1 & 4 & 5 & 6 \\ 12 & 2 & 3 & 4 & 6 \\ 13 & 2 & 3 & 5 & 6 \end{matrix} ] G(14, 7, 3) = [ \begin{matrix}0 & 5 & 6 & 7 & 8 & 9 & 12 & 13 \\ 1 & 6 & 8 & 9 & 10 & 11 & 12 & 13 \\ 2 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 3 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 4 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 5 & 0 & 6 & 8 & 10 & 11 & 12 & 13 \\ 6 & 0 & 1 & 5 & 7 & 9 & 10 & 11 \\ 7 & 0 & 2 & 3 & 4 & 6 & 10 & 11 \\ 8 & 0 & 1 & 2 & 3 & 4 & 5 & 13 \\ 9 & 0 & 1 & 2 & 3 & 4 & 6 & 12 \\ 10 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 11 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 12 & 0 & 1 & 2 & 3 & 4 & 5 & 9 \\ 13 & 0 & 1 & 2 & 3 & 4 & 5 & 8 \end{matrix} ]

G(14, 8, 3) = [ \begin{matrix}0 & 4 & 5 & 6 & 7 & 8 & 11 & 12 & 13 \\ 1 & 4 & 5 & 6 & 7 & 9 & 10 & 11 & 13 \\ 2 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 3 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 4 & 0 & 1 & 6 & 8 & 9 & 10 & 12 & 13 \\ 5 & 0 & 1 & 7 & 8 & 9 & 10 & 11 & 12 \\ 6 & 0 & 1 & 2 & 3 & 4 & 10 & 11 & 12 \\ 7 & 0 & 1 & 2 & 3 & 5 & 10 & 12 & 13 \\ 8 & 0 & 2 & 3 & 4 & 5 & 10 & 11 & 13 \\ 9 & 1 & 2 & 3 & 4 & 5 & 11 & 12 & 13 \\ 10 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 11 & 0 & 1 & 2 & 3 & 5 & 6 & 8 & 9 \\ 12 & 0 & 2 & 3 & 4 & 5 & 6 & 7 & 9 \\ 13 & 0 & 1 & 2 & 3 & 4 & 7 & 8 & 9 \end{matrix} ] G(15, 5, 4) = [ \begin{matrix}0 & 7 & 8 & 9 & 5 & 14 \\ 1 & 7 & 8 & 10 & 6 & 14 \\ 2 & 7 & 9 & 10 & 11 & 6 \\ 3 & 9 & 10 & 11 & 12 & 13 \\ 4 & 9 & 10 & 11 & 12 & 13 \\ 5 & 0 & 8 & 10 & 11 & 12 \\ 6 & 1 & 2 & 8 & 12 & 13 \\ 7 & 0 & 1 & 2 & 12 & 13 \\ 8 & 0 & 1 & 9 & 5 & 6 \\ 9 & 0 & 2 & 8 & 3 & 4 \\ 10 & 1 & 2 & 3 & 4 & 5 \\ 11 & 2 & 3 & 4 & 5 & 14 \\ 12 & 3 & 4 & 5 & 6 & 7 & 14 \\ 13 & 7 & 3 & 4 & 6 & 14 \\ 14 & 0 & 1 & 11 & 12 & 13 \end{matrix} ]

G(15, 6, 3) = [ \begin{matrix}0 & 7 & 8 & 9 & 10 & 11 & 12 \\ 1 & 7 & 8 & 9 & 12 & 13 & 14 \\ 2 & 7 & 10 & 11 & 12 & 13 & 14 \\ 3 & 8 & 9 & 10 & 11 & 12 & 13 \\ 4 & 8 & 9 & 10 & 11 & 12 & 14 \\ 5 & 8 & 9 & 10 & 11 & 13 & 14 \\ 6 & 8 & 9 & 10 & 11 & 13 & 14 \\ 7 & 0 & 1 & 2 & 12 & 13 & 14 \\ 8 & 0 & 1 & 3 & 4 & 5 & 6 \\ 9 & 0 & 1 & 3 & 4 & 5 & 6 \\ 10 & 0 & 2 & 3 & 4 & 5 & 6 \\ 11 & 0 & 2 & 3 & 4 & 5 & 6 \\ 12 & 0 & 1 & 2 & 3 & 4 & 7 \\ 13 & 1 & 2 & 3 & 5 & 6 & 7 \\ 14 & 1 & 2 & 4 & 5 & 6 & 7 \end{matrix} ] G(15, 7, 3) = [ \begin{matrix}0 & 1 & 2 & 3 & 4 & 5 & 7 & 8 \\ 1 & 0 & 2 & 3 & 4 & 5 & 7 & 8 \\ 2 & 0 & 1 & 3 & 4 & 5 & 6 & 13 \\ 3 & 0 & 1 & 2 & 4 & 5 & 6 & 12 \\ 4 & 0 & 1 & 2 & 3 & 5 & 6 & 11 \\ 5 & 0 & 1 & 2 & 3 & 4 & 6 & 10 \\ 6 & 2 & 3 & 4 & 5 & 7 & 9 & 14 \\ 7 & 0 & 1 & 6 & 8 & 9 & 10 & 11 & 14 \\ 8 & 0 & 1 & 7 & 9 & 12 & 13 & 14 \\ 9 & 6 & 7 & 8 & 10 & 11 & 12 & 13 \\ 10 & 5 & 7 & 9 & 11 & 12 & 13 & 14 \\ 11 & 4 & 7 & 9 & 10 & 12 & 13 & 14 \\ 12 & 3 & 8 & 9 & 10 & 11 & 13 & 14 \\ 13 & 2 & 8 & 9 & 10 & 11 & 12 & 14 \\ 14 & 6 & 7 & 8 & 10 & 11 & 12 & 13 \end{matrix} ]

G(15, 8, 3) = [ \begin{matrix}0 & 5 & 7 & 9 & 10 & 11 & 12 & 13 & 14 \\ 1 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 2 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 3 & 6 & 7 & 8 & 10 & 11 & 12 & 13 & 14 \\ 4 & 6 & 7 & 8 & 10 & 11 & 12 & 13 & 14 \\ 5 & 0 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ 6 & 1 & 2 & 3 & 4 & 9 & 11 & 12 & 14 \\ 7 & 0 & 1 & 2 & 3 & 4 & 9 & 10 & 14 \\ 8 & 1 & 2 & 3 & 4 & 5 & 9 & 13 & 14 \\ 9 & 0 & 1 & 2 & 5 & 6 & 7 & 8 & 14 \\ 10 & 0 & 1 & 2 & 3 & 4 & 5 & 7 & 12 \\ 11 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 13 \\ 12 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 10 \\ 13 & 0 & 1 & 2 & 3 & 4 & 5 & 8 & 11 \\ 14 & 0 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \end{matrix} ] G(16, 8, 3) = [ \begin{matrix}0 & 5 & 7 & 9 & 10 & 11 & 12 & 13 & 14 \\ 1 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 2 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 3 & 6 & 7 & 8 & 10 & 11 & 12 & 13 & 14 \\ 4 & 6 & 7 & 8 & 10 & 11 & 12 & 13 & 14 \\ 5 & 0 & 8 & 9 & 10 & 11 & 13 & 14 & 15 \\ 6 & 1 & 2 & 3 & 4 & 9 & 12 & 14 & 15 \\ 7 & 0 & 1 & 2 & 3 & 4 & 9 & 14 & 15 \\ 8 & 1 & 2 & 3 & 4 & 5 & 13 & 14 & 15 \\ 9 & 0 & 1 & 2 & 5 & 6 & 7 & 14 & 15 \\ 10 & 0 & 1 & 2 & 3 & 4 & 5 & 12 & 15 \\ 11 & 0 & 1 & 2 & 3 & 4 & 5 & 13 & 15 \\ 12 & 0 & 1 & 2 & 3 & 4 & 6 & 10 & 15 \\ 13 & 0 & 1 & 2 & 3 & 4 & 5 & 8 & 11 \\ 14 & 0 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 15 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \end{matrix} ]