| Abstract: | Za graf ▫$G$▫ obravnavamo postopek izgradnje dominacijske množice ▫$D$▫, kjer zaporedoma dodajamo po eno vozlišče tako, da vsakič, ko je novo vozlišče ▫$x$▫ dodano v množico ▫$D$▫, obstaja vozlišče ▫$y \in N_G[x]$▫, ki postane dominirano šele potem, ko smo ▫$x$▫ dodali v ▫$D$▫. Največja kardinalnost množice ▫$D$▫, dobljene na opisani način, se imenuje Grundyjevo dominacijsko število grafa ▫$G$▫, množici ▫$D$▫ pa rečemo Grundyjeva dominacijska množica grafa ▫$G$▫. Grundyjeva dominacijska množica povezanega grafa ni nikoli enolična, razen pri trivialnem grafu, zato obravnavamo naravno šibkejšo različico enoličnosti, pri kateri ne ločimo med dvema Grundyjevima dominacijskima množicama grafa ▫$G$▫, če obstaja avtomorfizem grafa ▫$G$▫, ki preslika eno v drugo. Obe različici enoličnosti obravnavamo glede na več konceptov Grundyjeve dominacije, ki so se pojavili v kontekstu raziskav dominacijske igre in so tesno povezani tudi z ničelno prisilo. Za vsako od štirih inačic Grundyjeve dominacije okarakteriziramo grafe, ki imajo natanko eno Grundyjevo dominacijsko množico ustreznega tipa, ter tudi tiste gozdove, ki zadoščajo šibkejšemu (na avtomorfizmih temelječemu) pogoju enoličnosti. Slednje karakterizacije vodijo do učinkovitih algoritmov za prepoznavanje pripadajočih razredov gozdov. |
|---|
