ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 9 (2015) 187-195
Bounds on the domination number of Kneser graphs
Patrie R. J. Östergärd *
Department of Communications and Networking, Aalto University School of Electrical Engineering, P.O. Box 13000, 00076 Aalto, Finland
Zehui Shao f
Key Laboratory of Pattern Recognition and Intelligent Information Processing, Institutions ofHigher Education ofSichuan Province, School ofInformation Science and Technology, Chengdu University, Chengdu, 610106, China
Received 14 May 2013, accepted 17 August 2014, published online 28 November 2014
The Kneser graph KG„jfc has one vertex for each k-subset of an n-set and edges between vertices whenever the corresponding subsets are disjoint. A dominating set in a graph G = (V, E) is a subset S C V such that each vertex in V \ S is adjacent to at least one vertex in S. The domination number of KGn k, denoted by y(n, k), is the minimum size of a dominating set in that graph. Combinatorial and computer-aided techniques for obtaining bounds on 7(n, k) are here considered, and several new bounds are obtained. An updated table of bounds on 7(n, k) is presented for n < 21 and k < 5.
Keywords: Dominating set, domination number, Kneser graph. Math. Subj. Class.: 05C69, 05C35
* Corresponding author. Supported in part by the Academy of Finland, Grant No. 132122. t Supported by the National Natural Science Foundation of China, Grant No. 61309015. E-mail addresses: patric.ostergard@aalto.fi (Patric R. J. Ostergard), zshao@cdu.edu.cn (Zehui Shao), xxdmaths@sina.com (Xiaodong Xu)
Xiaodong Xu
Guangxi Academy ofScience, Nanning, Guangxi 530007, China
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
79
Ars Math. Contemp. 9 (2015) 165-186
1	Introduction
Let G = (V, E) be a simple graph, that is, a graph having neither loops nor multiple edges. A dominating set in G is a subset S c V such that each vertex in V\S is adjacent to at least one vertex in S. The domination number y(G) of G is the minimum size of a dominating set in G. The domination number has been extensively studied in the general case [11]. Due to a variety of applications, the case of n-cubes, G = Qn, is of particular interest [3]; most of the early work considered such graphs. In the current work, another specific type of graphs is considered, namely Kneser graphs.
The Kneser graph KG„jfc has one vertex for each k-subset of an n-set and edges between vertices whenever the corresponding subsets are disjoint. If n < 2k, then KG„,fc has no edges, so we assume that n > 2k. We further denote the domination number of KG„,fc by y(n, k). See [6, Chap. 7] for an in-depth discussion of Kneser graphs.
General and specific bounds on y(n, k) have been considered in a sequence of studies, including [2, 8, 10, 12, 18]. However, several of the best known bounds for small parameters were rather weak prior to this study. Indeed, the aim of the current work is to apply combinatorial and computer-aided techniques to the problem of improving upper and lower bounds on the domination number of Kneser graphs—and occasionally even find the exact value when the bounds meet.
A total dominating set in a graph G = (V, E) is a subset S c V such that each vertex in V is adjacent to at least one vertex in S. The minimum size of a total dominating set is called the total domination number, and the total domination number of KG„,fc is denoted by Yt(n, k). It is obvious that
Y(n,k) < Yt(n,k).	(1.1)
Let C(v, k, t) denote the smallest number of k-subsets of a v-set, such that every t-subset of the v-set occurs in at least one of the k-subsets. Then Yt(n, k) = C(n, n - k, k), so by (1.1),
Y(n,k) < C(n, n - k,k).	(1.2)
Exact values of and upper bounds on C(v, k, t) for v < 32, k < 16, and t < 5 can be found in [7].
The paper is organized as follows. Methods for obtaining upper and lower bounds on Y(n, k) are considered in Sections 2 and 3, respectively. The results are summarized in Section 4, where an updated table of bounds on Y(n, k) is presented for n < 21 and k < 5.
2	Upper Bounds and Exact Values
Upper bounds for the domination number are commonly constructive, that is, explicit dominating sets prove the bounds. We here present various general results for upper bounds on Y(n, k); in some of the theorems, the exact value is in fact obtained. If n < 2k, then the Kneser graph consists of isolated vertices only. In the first nontrivial case, n = 2k, a dominating set must contain one vertex from each pair of disjoint k-sets.
Theorem 2.1. For any k,
1 /2k
Y(2k,k)=Hk
It is easy to show that if n is large enough, then the smallest dominating set is obtained by taking k +1 disjoint k-sets.
Patrie R. J. Ôstergârd et al.: Bounds on the domination number ofKneser graphs
189
Theorem 2.2. If n > k2 + k, then y(n, k) = k + 1.
The exact value of Y(n, k) has also been determined for a range of values of n smaller than those covered by Theorem 2.2.
Theorem 2.3 ([10]). If k > 3 and f k2 + k < n < k2 + k, then
Y(n,k) = k + 1 +
k2 + k — n
lk/2j
With increasing n, Y(n, k) turns out to be nonincreasing.
Theorem 2.4 ([8, Proposition 4.2.4]). If n > 2k + 1, ihen Y(n + 1, k) < 7(n, k). Theorem 2.5 ([8, Theorem 4.5.1]). fk > 4 and7(n, k) < min{2k,n-k}, then Y(n, k) =
Yt(n,k).
We shall next see how dominating sets in certain Kneser graphs are related to a coloring problem for hypergraphs that has been extensively studied. We consider the case n = 2k + 1—such Kneser graphs are known as odd graphs—and view a dominating set S of the graph KG2k+1,k as the set of hyperedges in a hypergraph G' = (V', E') with | V= n, |E'| = |S|, and edges of size k (so the hypergraph is k-uniform).
Now consider an arbitrary balanced coloring of the vertices in V' with two colors, that is, k of the vertices are colored with one color and k + 1 with the other [21]. Since the vertex in the original Kneser graph that is labelled by the subset of the k vertices with the first color is dominated by some vertex s g S, the hyperedge in E' corresponding to s is unicolor. Hence, G' does not have a balanced coloring with two colors so that no hyperedge is unicolor, that is, G' is not 2-colorable in a balanced way.
Hypergraphs that are 2-colorable (without requiring that the colorings be balanced) are said to have property B [13, Sect. 15.1]. Consequently, a hypergraph with appropriate parameters that does not have property B gives a dominating set in KG2fc+1fc. Actually, this implication goes in the other direction as well.
The upward shadow of a (k - 1)-subset of an n-set is the collection of all k-subsets of the n-set that contain the (k - 1)-subset.
Lemma 2.6 ([8, Lemma 4.2.3]). If n > 2k + 1, then there exists a dominating set attaining Y (n, k) that does not contain the upward shadow of any (k — 1)-subset of the n-set.
Theorem 2.7. There exists a dominating set S attaining Y(2k + 1, k) that can be trans-formedintoa k-uniform hypergraph G' = (V, E) with |V | = 2k + 1 and |E| = |S | without property B.
Proof. Consider the hypergraph G' = (V', E') obtained from a dominating set attaining Y(2k +1, k) that does not contain the upward shadow of any (k — 1)-set. Such a dominating set exists by Lemma 2.6.
If the vertices in V' are colored in a balanced way, then since the hypergraph was constructed from a dominating set in KG2k+1,k, there exists a unicolor hyperedge.
Now consider a coloring of the vertices V' with k + 2 and k — 1 vertices of the two colors and denote the vertices in the former color class by U. If no hyperedge in E' is a subset of U, then the same holds for each (k + 1)-subset of U, so by the existence of a balanced coloring we get that (V' \ U) u v g E' for all v g U. But this is then an
81
Ars Math. Contemp. 9 (2015) 165-186
upward shadow and we have a contradiction (so a hyperedge that is a subset of U is indeed unicolor).
The colorings with classes of size a and n — a where a > k + 3 are handled by considering an arbitrary subset of the larger class of size k + 2 and using the previous
By Theorem 2.7 and results by Abbott and Liu [1] we now get that 24 < y(9, 4) < 26. Note, however, that in certain studies on uniform hypergraphs without property B a further assumption is made that the hyperedges must contain all pairs of vertices. Results for that variant of the problem, which is motivated by a more general question regarding property B, are not directly applicable here. This includes the results in [16, 21].
For certain parameters, we can say a lot about Y(2k + 1, k). Let 2 < t < k < v. An S(t, k, v) Steiner system is a collection of k-sets out of a v-set with the property that every t-subset of the v-set occurs in exactly one of the k-sets. The following result has been discussed both in the context of hypergraphs without property B [4] and dominating sets in KG2fc+i,fc [9]; see also [5, Lemma 11.8.3].
Theorem 2.8. There is a Steiner system S (k — 1, k, 2k + 1) if and only if
One may further use partial or exhaustive computational methods to determine bounds on y(n, k). Since upper bounds can be proven by finding a structure attaining the bound, nonexhaustive methods can be applied to such cases. For lower bounds, on the other hand, exhaustive methods are required; we shall consider such methods in the next section.
In [19], the tabu search metaheuristic is applied to the problem of finding dominating sets in n-cubes. The algorithm takes the parameters of the instance and the desired size of the dominating set (which is, for example, one less than the best known upper bound), and searches for such a dominating set. The algorithm is also applicable to Kneser graphs—in fact, it is applicable to arbitrary graphs. The reader should consult [19] for details. Structures obtained in the current work and leading to new upper bounds on y(n, k) are listed in the Abstract. Some of the best known structures turn out to have nontrivial symmetries; these could further be used to narrow down the search space.
We consider symmetries of dominating sets in terms of the labels (subsets) of the vertices. Two dominating sets are said to be equivalent if there is a permutation of the n-set that maps the vertices of one dominating set onto the vertices of the other. Such a mapping from a dominating set onto itself is an automorphism, and the set of all automorphisms of a dominating set forms the automorphism group of the dominating set. Such an automorphism group is isomorphic to a subgroup of the stabilizer subgroup of the dominating set in Aut(KGn,k). Note that it may happen that the automorphism group is a proper such subgroup; consider, for example, the mapping of the k-subsets of a 2k-set to their complements. The nauty software [17] is a useful computational tool in this context.
3 Lower Bounds
Several of the bounds in the previous section can be used also to get lower bounds. We shall here state two more general results that can be used to get best known lower bounds for small parameters. The first of these is the well-known volume bound obtained by dividing the total number of vertices with the number of vertices dominated by a single vertex.
argument.
□
Patrie R. J. Ôstergârd et al.: Bounds on the domination number ofKneser graphs
189
Theorem 3.1. For any n and k,
(n)
Y(n,k) > -.
' ) > 1 + (V)
Theorem 3.2 ([8, Lemma 4.5.3]). Assume that n = ak, where a, k > 2. Then
a
Y(n, k) > --(y(n + k, k) — 1).
a-1
To simplify the discussion of the techniques to obtain lower bounds on y(n, k), it is useful to think of a dominating set as a constant weight code [20]. The codewords of this code are of length n and have 1s in the coordinates given by the corresponding k-subset and 0s in the other coordinates. Theory and terminology from coding theory can then be directly applied.
There are three general approaches to exhaustively search for codes with prescribed parameters [15, Chap. 7]: via subcodes, codeword by codeword, and coordinate by coordinate. There is no obvious way of constructing the current type of codes via subcodes, that is, codes obtained by considering the codewords with a 1 (alternatively, 0) in a given coordinate and deleting that coordinate. Some results can indeed be obtained in a backtrack search constructing the code word by word as in [24], which can be consulted for general details.
The origins of the method of constructing codes coordinate by coordinate can be traced back to the 1960s [14], after which it has been developed further and become an efficient tool in the study of dominating sets, in particular in n-cubes and related graphs [22, 23]. See also [15, Sect. 7.2.2]. A version that has been applied to the hypergraph coloring problem discussed in the previous section can be found in [21].
The idea in the coordinate by coordinate approach can be described as a generalization of the following theorem.
Theorem 3.3. Let D be a dominating set in KGn,k, and let D = D0 u D1 such that Di consists of the vertices whose label has an i in the first coordinate. Then
1. |Di| + (n-k-1)|Do|> (k-1),
2. miDi+(i+m) Doi> Ckx).
Proof. Let G = (V, E) be the KG„,fc Kneser graph, and let V = (0 u V so that the labels of the vertices in V have an i in the first coordinate. Then |V0| = ("k1) and |V11 = (^Z ^. The result now follows as each vertex in D0 dominates 1 + )" -1 - fc) vertices in V0 and ("kfc) vertices in V1, and each vertex in D1 dominates	vertices in V0 and 1 vertex
in V1.	□
Theorem 3.3 can be generalized to an arbitrary number of specified coordinates. For example, with two specified coordinates we let D = D00 u D01 u D10 u D11, V = V00 u V01 u V10 u V11 and get four inequalities. For a small number of coordinates, the inequalities can be derived by hand, but when the number gets larger, it is convenient to form these computationally.
When a code is constructed coordinate by coordinate, one first fixes the number of codewords and then start from the distributions of 0s and 1s in the first coordinate given by
83
Ars Math. Contemp. 9 (2015) 165-186
Theorem 3.3. In a backtrack exhaustive search, one may for the next couple of coordinates solve larger and larger systems of equations, but at some point one may start checking all possible candidates for the next coordinate and see whether the inequalities are fulfilled. At each level of the search tree, isomorph rejection should be carried out. For the sake of efficiency, one may also require that the number of 1s in the coordinates is either increasing or decreasing. Except for minor differences in details, the approach in [21] can be used.
4 Results
Table 1 summarizes the best known bounds on and exact values for 7(n, k), n < 21, k < 5. Indices are added to the entries, to give explanations of lower and upper bounds. If a bound can be obtained in several ways, we pick the explanation that in some sense is the nicest. We omit the index when the bound follows from Theorem 2.2.
Table 1: Bounds on 7(n, k) for n < 21, k < 5
n\k	2	3	4	5
4	a3°			
5	c3c			
6	3	a10a		
7	3	eye		
8	3	cyc	a35a	
9	3	m 7c	j to 1	
10	3	b66	c15k	a126a
11	3	656	n5c	e66e
12	3	4	®12h	®37-56fc
13	3	4	m 10^	j23-39k
14	3	4	dgh	f16—31k
15	3	4	dgh	g15-27h
16	3	4	676	®12-22h
17	3	4	676	c11—17h
18	3	4	b66	c11—15h
19	3	4	b66	c11—14h
20	3	4	5	c11—12h
21	3	4	5	d11—12h
Patrie R. J. Ôstergârd et al.: Bounds on the domination number ofKneser graphs
189
Key to Table 1.
Unmarked bounds are from Theorem 2.2.
Bounds: a Theorem 2.1 b Theorem 2.3 c Theorem 2.4 d Theorem 2.5 and [7] e Theorem 2.8 f Theorem 3.1 g Theorem 3.2 h Eq. (1.2) and [7]
1 Exhaustive search, coordinate by coordinate j Exhaustive search, word by word k New constructive result, see Appendix 1 Abbott and Liu [1] (Theorem 2.7) m Gorodezky [8]
Appendix
We here list the structures that lead to new upper bounds on j(n, k). We first present structures that can be described as a set of orbits under the action of a permutation group, and finally list some explicit structures (we do not exclude the possibility that these, or better, bounds could also be obtained by a structure with some symmetry).
Y(10,4) < 15:
Generator of group: (1 2 3 4 5)(6 7 8 9 10)
Orbit representatives: 1110010000, 1010000110, 1000001101
Y(13, 5) < 39:
Generator of group: (1 2 3 4 5 6 7 8 9 10 11 12 13)
Orbit representatives: 1101011000000, 1110001001000, 1101000100010
Y(12, 5) < 56:
111000110000, 100000111100, 010001011001, 010000111010, 001010000111, 011100010001, 110101000010, 100011010100, 000011111000, 110100100001, 110011001000, 011101001000, 101011001000, 000001100111, 011000100110, 110000010110, 001001100011, 100110001100, 111110000000, 000110010110, 100001101001,010011100001,010100001101,000010011011, 000111100100, 001110110000, 010101010100, 101010010001, 001110001010, 001000111010, 011011000010, 001100001101, 100101001010, 001001011001, 010110001010, 100001010011, 011010100001, 101000101100, 000100101011, 110000101100, 010010000111, 101101000010,011001000101, 100100110001, 100010000111, 011000011100, 110010010001, 010011100100, 101000010110, 000100011101, 000101110010, 101100100001, 001011100100, 111000001010, 001101010100, 010110110000
85
Ars Math. Contemp. 9 (2015) 165-186
Y(14, 5) < 31:
10000011001100,00011110100000, 11100100100000, 00110101000010, 00110110000001, 00001011000110, 00010010100110, 01000011000011, 00000101101100,01011000010100, 10110000010001, 00100000100111, 10001010011000, 01101010000001, 01100010011000, 01010100011000, 11000000001101, 10010000101010, 01100001010100, 00001001110001, 10001111000000, 01001010110000, 00000001011011, 10000100010110, 11001100000010, 00101000101010, 00001100001101, 10111001000000, 01010001100001, 10000110110000, 00011010001100
References
[1]	H. L. Abbott and A. C. Liu, On property B of families of sets, Canad. Math. Bull. 23 (1980), 429-435.
[2]	E. Clark, Domination in Kneser graphs, unpublished manuscript, 1988.
[3]	G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein, Covering Codes, North-Holland, Amsterdam, 1997.
[4]	H. L. de Vries, On property B and on Steiner systems, Math. Z. 153 (1977), 155-159.
[5]	C. D. Godsil, Algebraic Combinatorics, Chapman & Hall, New York, 1993.
[6]	C. Godsil and G. Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001.
[7]	D. M. Gordon and D. R. Stinson, Coverings, in: C. J. Colbourn and J. H. Dinitz (eds.), Handbook of Combinatorial Designs, 2nd ed., Chapman & Hall/CRC, Boca Raton, 2007, 365-373.
[8]	I. Gorodezky, Domination in Kneser graphs, Master's thesis, University of Waterloo, Canada, 2007.
[9]	P. Hammond and D. H. Smith, Perfect codes in the graphs Ok, J. Combin. Theory Ser. B 19 (1975), 239-255.
[10]	C. Hartman and D. B. West, Covering designs and domination in Kneser graphs, unpublished manuscript, 2003.
[11]	T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[12]	J. Ivanco and B. Zelinka, Domination in Kneser graphs, Math. Bohem. 118 (1993), 147-152.
[13]	T. R. Jensen and B. Toft, Graph Coloring Problems, Wiley, New York, 1995.
[14]	H. J. L. Kamps and J. H. van Lint, The football pool problem for 5 matches, J. Combin. Theory 3 (1967), 315-325.
[15]	P. Kaski and P. R. J. Ostergard, Classification Algorithms for Codes and Designs, Springer, Berlin, 2006.
[16]	G. Manning, The M (4) problem of Erdos and Hajnal, Ph.D. dissertation, Northern Illinois University, 1997.
[17]	B. D. McKay, nauty user's guide (version 1.5), Technical Report TR-CS-90-02, Computer Science Department, Australian National University, Canberra, 1990.
[18]	J. C. Meyer, Quelques problemes concernant les cliques des hypergraphes h-complets et q-parti h-complets, in: C. Berge and D. Ray-Chaudhuri (eds.), Hypergraph Seminar, Lecture Notes in Mathematics, Vol. 411. Springer-Verlag, Berlin, 1974, 127-139.
[19]	P. R. J. (Ostergard, Constructing covering codes by tabu search, J. Combin. Des. 5 (1997), 7180.
Patrie R. J. Ôstergârd et al.: Bounds on the domination number ofKneser graphs
189
[20]	P. R. J. Ostergard, Classification of binary constant weight codes, IEEE Trans. Inform. Theory 56 (2010), 3779-3785.
[21]	P. R. J. (Ostergard, On the minimum size of 4-uniform hypergraphs without property B, Discrete Appl. Math. 163 (2014), 199-204.
[22]	P. R. J. (Ostergard and U. Blass, On the size of optimal binary codes of length 9 and covering radius 1, IEEE Trans. Inform. Theory 47 (2001), 2556-2557.
[23]	P. R. J. (Ostergard and A. Wassermann, A new lower bound for the football pool problem for 6 matches, J. Combin. Theory Ser. A 99 (2002), 175-179.
[24]	P. R. J. (Ostergard and W. D. Weakley, Classification of binary covering codes, J. Combin. Des. 8 (2000), 391-401.