| Title: | Graphs with unique Grundy dominating sets |
|---|
| Authors: | ID Brešar, Boštjan (Author)
ID Dravec, Tanja (Author) |
|---|
| Files: |  PDF - Presentation file, download (490,32 KB)
MD5: 53C31C2235052FCEC0F49EC3030776E8
 URL - Source URL, visit https://link.springer.com/article/10.1007/s40314-026-03835-w
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | Grundy total domination number, Grundy domination number, zero forcing number, trees, graph automorphism |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.12.2026 |
|---|
| Year of publishing: | 2026 |
|---|
| Number of pages: | 20 str. |
|---|
| Numbering: | Vol. 45, iss. 10, article no. 444 |
|---|
| PID: | 20.500.12556/DiRROS-30350  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 2238-3603 |
|---|
| DOI: | 10.1007/s40314-026-03835-w |
|---|
| COBISS.SI-ID: | 282411011 |
|---|
| Note: |
|
|---|
| Publication date in DiRROS: | 22.06.2026 |
|---|
| Views: | 22 |
|---|
| Downloads: | 13 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
