Bounds on the domination number of Kneser graphs - Östergard, Patric R. J. (Ars mathematica contemporanea, 2015)
Kneserjev graf ?${\rm KG}_{n,k}$?, k ima po eno vozlišče, prirejeno vsaki ?$k$?-podmnožici ?$n$?-množice; ta vozlišča so povezana natanko takrat, ko so ustrezne podmnožice disjunktne. Dominirajoča množica v grafu ?$G=(V, E)$? je podmnožica ?$S \subseteq V$? z lastnostjo, da je vsako vozlišče v ?$V \setminus S$? sosedno najmanj enemu vozlišču iz ?$S$?. Dominacijsko število ?$γ(n, k)$? grafa ?${\rm KG}_{n,k}$? je velikost najmanjše dominirajoče množice v tem grafu. V tem članku obravnavamo kombinatorične in računalniško podprte tehnike za določanje mej ?$γ(n, k)$?, in z njimi dobimo mnoge nove meje. Predstavimo tudi osveženo tabelo mej ?$γ(n, k)$? za ?$n \le 21$? in ?$k \le 5$?.
Keywords: dominating set; domination number; dominirajoča množica; dominirajoče število; Kneser graph; Kneserjev graf