Bounds on the domination number of Kneser graphs

Patric R. J. Östergård, Zehui Shao, Xiaodong Xu


The Kneser graph KGn, k 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 ⊆ V such that each vertex in V \ S is adjacent to at least one vertex in S. The domination number of , denoted by γ(n, k), is the minimum size of a dominating set in that graph. Combinatorial and computer-aided techniques for obtaining bounds on γ(n, k) are here considered, and several new bounds are obtained. An updated table of bounds on γ(n, k) is presented for n ≤ 21 and k ≤ 5.


Dominating set, domination number, Kneser graph.

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications