| Naslov: | Graphs with unique Grundy dominating sets |
|---|
| Avtorji: | ID Brešar, Boštjan (Avtor)
ID Dravec, Tanja (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (490,32 KB)
MD5: 53C31C2235052FCEC0F49EC3030776E8
 URL - Izvorni URL, za dostop obiščite https://link.springer.com/article/10.1007/s40314-026-03835-w
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | 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. |
|---|
| Ključne besede: | Grundy total domination number, Grundy domination number, zero forcing number, trees, graph automorphism |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.12.2026 |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | 20 str. |
|---|
| Številčenje: | Vol. 45, iss. 10, article no. 444 |
|---|
| PID: | 20.500.12556/DiRROS-30350  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 2238-3603 |
|---|
| DOI: | 10.1007/s40314-026-03835-w |
|---|
| COBISS.SI-ID: | 282411011 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 22.06.2026 |
|---|
| Število ogledov: | 18 |
|---|
| Število prenosov: | 11 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
