Abstract | ||
---|---|---|
The Kneser graph KG(n,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 subset of V such that each vertex in V \ S is adjacent to at least one vertex in S. The domination number of KG(n,k), denoted by gamma (n, k), is the minimum size of a dominating set in that graph. Combinatorial and computer-aided techniques for obtaining bounds on gamma(n, k) are here considered, and several new bounds are obtained. An updated table of bounds on gamma(n, k) is presented for n <= 2 1 and k <= 5. |
Year | Venue | Keywords |
---|---|---|
2015 | ARS MATHEMATICA CONTEMPORANEA | Dominating set,domination number,Kneser graph |
Field | DocType | Volume |
Topology,Discrete mathematics,Graph,Dominating set,Combinatorics,Disjoint sets,Vertex (geometry),Domination analysis,Kneser graph,Mathematics | Journal | 9 |
Issue | ISSN | Citations |
2 | 1855-3966 | 1 |
PageRank | References | Authors |
0.38 | 2 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Patric R. J. Östergård | 1 | 609 | 70.61 |
Zehui Shao | 2 | 119 | 30.98 |
Xiaodong Xu | 3 | 26 | 9.91 |