Grundy domination and zero forcing in Kneser graphs

angleški

2019

letnik 17, številka 2

Grundyjevo celotno dominatno število   Grundyjevo dominantno število   Kneserjev graf   najmanjši rang   število ničelne prisile

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

V članku nadaljujemo z raziskavami različnih tipov (Grundyjevih) dominacijskih zaporedij. Obravnavamo štiri različne tipe Grundyjevih dominantnih števil in njim sorodna števila ničelne prisile, pri čemer se osredotočamo na ta števila v dobro znanih Kneserjevih grafih ?$K_{n,r}$?. Med drugim ugotovimo, da je Grundyjevo celotno dominantno število ?$\gamma_{\rm gr}^t(K_{n,r})$? enako ?${{2r}\choose {r}}$? za vsaka ?$r\ge 2$? in ?$n\ge 2r+1$?. Za Grundyjevo dominantno število Kneserjevega grafa dobimo, da je ?$\gamma_{\rm gr}(K_{n,r})=\alpha(K_{n,r})$?, če je le ?$n$? dovolj veliko število v primerjavi z ?$r$?. Dokažemo tudi, da je število ničelne prisile ?$Z(K_{n,r})$? enako ?${{n}\choose{r}}-{{2r}\choose{r}}$?, ko je ?$n\ge 3r+1$? in ?$r\ge 2$?, medtem ko za ?$Z(K_{n,r})$?, ko je ?$2r+1\le n\le 3r$?, najdemo spodnje in zgornje meje. Spotoma dobimo tudi nekaj spodnjih mej za različne tipe najmanjših rangov Kneserjevih grafov.

29.05.2020