Bounds on the domination number of Kneser graphs

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

Abstract


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.

Keywords


Dominating set, domination number, Kneser graph.

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.491.b02

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