20.500.12556/DKUM-98609 Graphs with unique Grundy dominating sets Grafi z enoličnimi Grundyjevimi dominacijskimi množicami Given a graph ▫$G$▫ consider a procedure of building a dominating set ▫$D$▫ in ▫$G$▫ by adding vertices to ▫$D$▫ one at a time in such a way that whenever vertex ▫$x$▫ is added to ▫$D$▫ there exists a vertex ▫$y\in N_G[x]$▫ that becomes dominated only after ▫$x$▫ is added to ▫$D$▫. The maximum cardinality of a set ▫$D$▫ obtained in the described way is called the Grundy domination number of ▫$G$▫ and ▫$D$▫ a Grundy dominating set. While a Grundy dominating set of a connected graph ▫$G$▫ is not unique unless ▫$G$▫ is the trivial graph, we consider a natural weaker uniqueness condition, notably that for every two Grundy dominating sets in a graph ▫$G$▫ there is an automorphism that maps one to the other. We investigate both versions of uniqueness for several concepts of Grundy domination, which appeared in the context of domination games and are also closely related to zero forcing. For each of the four variations of Grundy domination we characterize the graphs that have only one Grundy dominating set of the given type, and characterize those forests that enjoy the weaker (isomorphism based) condition of uniqueness. The latter characterizations lead to efficient algorithms for recognizing the corresponding classes of forests. 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. Grundy total domination number Grundy domination number zero forcing number trees graph automorphism Grundyjevo celotno dominacijsko število Grundyjevo dominacijsko število število ničelne prisile drevesa avtomorfizem grafa true false true Sociedade Brasileira de Matemática Aplicada e Computacional Angleški jezik Slovenski jezik Znanstveno delo 2026-06-24 06:53:52 2026-08-31 14:43:08 2026-09-01 03:08:22 0000-00-00 00:00:00 2026 0 São Carlos 0 20 str. št. 10, št. članka 444 Letn. 45 dec. 2026 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 2026-05-31 2026-06-20 519.17 282411011 10.1007/s40314-026-03835-w 2238-3603 RAZ_Bresar_Bostjan_2026.pdf RAZ_Bresar_Bostjan_2026.pdf 1 0865E744257F6584529DEB6156BB420A d7f174aea8de36122a73583a36af353a96c25de2386cbd8a443792e60c9d95da 5f544083-a539-11f1-b1f1-00155d0001be https://dk.um.si/Dokument.php?lang=slv&id=211044 https://link.springer.com/article/10.1007/s40314-026-03835-w 1 b279316f-6f88-11f1-868d-00155d580e34 https://dk.um.si/Dokument.php?lang=slv&id=207520 Fakulteta za naravoslovje in matematiko 0 0 0