259 KB20 KB200820252015Östergard, Patric R. J.Shao, ZehuiXu, Xiaodongštevilka:2letnik:9str. 187-195COBISSID:17588825ISSN:1855-3966URN:URN:NBN:SI:doc-G3YP01PEenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneadominating setdomination numberdominirajoča množicadominirajoče številoKneser graphKneserjev grafBounds on the domination number of Kneser graphs|The Kneser graph ?${\rm 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 \subseteq V$? such that each vertex in ?$V \setminus S$? is adjacent to at least one vertex in ?$S$?. The domination number of ?${\rm 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 \le 21$? and ?$k \le 5$?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$?TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije