Grundy double domination number: bounds, graph operations, and efficient computation for $P_4$-tidy graphs
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915360024821760 |
|---|---|
| author | Torres, Pablo |
| author_facet | Torres, Pablo |
| contents | Inspired by graph domination games, various domination-type vertex sequences have been introduced, including the Grundy double dominating sequence (GDDS) of a graph and its associated parameter, the Grundy double domination number (GDDN). The decision version of the problem of computing the GDDN is known to be NP-complete, even when restricted to split graphs and bipartite graphs. In this paper, we establish general tight bounds for the GDDN. We also describe GDDSs for vertex-removed graphs and for the join of two graphs. Applying these results, we prove that computing the GDDN is linear for $P_4$-tidy graphs, thereby solving an open problem previously posed for cographs by B. Brešar et al. in [Brešar, B., Pandey, A., and Sharma, G. (2022). Computational aspects of some vertex sequences of grundy domination-type. Indian J. Discrete Math., 8:21-38]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_21235 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Grundy double domination number: bounds, graph operations, and efficient computation for $P_4$-tidy graphs Torres, Pablo Combinatorics 05C69, 05C76 Inspired by graph domination games, various domination-type vertex sequences have been introduced, including the Grundy double dominating sequence (GDDS) of a graph and its associated parameter, the Grundy double domination number (GDDN). The decision version of the problem of computing the GDDN is known to be NP-complete, even when restricted to split graphs and bipartite graphs. In this paper, we establish general tight bounds for the GDDN. We also describe GDDSs for vertex-removed graphs and for the join of two graphs. Applying these results, we prove that computing the GDDN is linear for $P_4$-tidy graphs, thereby solving an open problem previously posed for cographs by B. Brešar et al. in [Brešar, B., Pandey, A., and Sharma, G. (2022). Computational aspects of some vertex sequences of grundy domination-type. Indian J. Discrete Math., 8:21-38]. |
| title | Grundy double domination number: bounds, graph operations, and efficient computation for $P_4$-tidy graphs |
| topic | Combinatorics 05C69, 05C76 |
| url | https://arxiv.org/abs/2506.21235 |