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 ?$\gamma(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 ?$\gamma(n, k)$?, in z njimi dobimo mnoge nove meje. Predstavimo tudi osveženo tabelo mej ?$\gamma(n, k)$? za ?$n \le 21$? in ?$k \le 5$?.

Pravice

URN

URN:NBN:SI:DOC-G3YP01PE

COBISSID

17588825

Objavljeno

29.05.2020

Metapodatki

Citiranje

APA:

Östergard, Patric R. J., Shao, Zehui, Xu, Xiaodong (2015). Bounds on the domination number of Kneser graphs. Ars mathematica contemporanea, letnik 9, številka 2, str. 187-195. URN:NBN:SI:DOC-G3YP01PE from http://www.dlib.si

MLA:

Östergard, Patric R. J., Shao, Zehui, Xu, Xiaodong. "Bounds on the domination number of Kneser graphs." Ars mathematica contemporanea letnik 9. številka 2 (2015) str. 187-195.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-G3YP01PE>

Ars mathematica contemporanea
2008-
(Zbirni zapis)