Geodesic
Bounds on the domination number of Kneser graphs
Ars Mathematica Contemporanea, Tome 9 (2015) no. 2, pp. 187-195.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.491.b02
Keywords: Dominating set, domination number, Kneser graph. 
@article{10_26493_1855_3974_491_b02,
     author = {Patric R. J. \"Osterg\r{a}rd and Zehui Shao and Xiaodong Xu},
     title = {Bounds on the domination number of {Kneser} graphs},
     journal = {Ars Mathematica Contemporanea},
     pages = {187--195},
     publisher = {mathdoc},
     volume = {9},
     number = {2},
     year = {2015},
     doi = {10.26493/1855-3974.491.b02},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.491.b02/}
}
TY  - JOUR
AU  - Patric R. J. Östergård
AU  - Zehui Shao
AU  - Xiaodong Xu
TI  - Bounds on the domination number of Kneser graphs
JO  - Ars Mathematica Contemporanea
PY  - 2015
SP  - 187
EP  - 195
VL  - 9
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.491.b02/
DO  - 10.26493/1855-3974.491.b02
LA  - en
ID  - 10_26493_1855_3974_491_b02
ER  - 
%0 Journal Article
%A Patric R. J. Östergård
%A Zehui Shao
%A Xiaodong Xu
%T Bounds on the domination number of Kneser graphs
%J Ars Mathematica Contemporanea
%D 2015
%P 187-195
%V 9
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.491.b02/
%R 10.26493/1855-3974.491.b02
%G en
%F 10_26493_1855_3974_491_b02
Patric R. J. Östergård; Zehui Shao; Xiaodong Xu. Bounds on the domination number of Kneser graphs. Ars Mathematica Contemporanea, Tome 9 (2015) no. 2, pp. 187-195. doi : 10.26493/1855-3974.491.b02. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.491.b02/

Cité par Sources :