Grundy dominating sequences and zero forcing sets
Discrete Optimization · 2017-11 · 26 · 66-77
DOI: 10.1016/j.disopt.2017.07.001 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Optimization, 2017-11. Verfasst von Boštjan Brešar und 7 weiteren Autor:innen. Die Arbeit wurde bisher 27-mal zitiert (Crossref) und nennt 26 Literaturangaben. Gefördert von: Slovenian Research Agency, National Research, Development and Innovation Office – NKFIH, Hungarian Academy of Sciences.
Abstract (Originalsprache)
If G is a graph, then a sequence v 1 , … , v m of vertices is a closed neighborhood sequence if for all 2 ≤ i ≤ m we have N [ v i ] ⁄ ⊆ ∪ j = 1 i − 1 N [ v j ] , and it is an open neighborhood sequence if for all 2 ≤ i ≤ m we have N ( v i ) ⁄ ⊆ ∪ j = 1 i − 1 N ( v j ) . The length of a longest closed (open) neighborhood sequence is the Grundy (Grundy total) domination number of G . In this paper we introduce two similar concepts in which the requirement on the neighborhoods is changed to N ( v i ) ⁄ ⊆ ∪ j = 1 i − 1 N [ v j ] or N [ v i ] ⁄ ⊆ ∪ j = 1 i − 1 N ( v j ) . In the former case we establish a strong connection to the zero forcing number of a graph, while we determine the complexity of the decision problem in the latter case. We also study the relationships among the four concepts, and discuss their computational complexities.
Förderung
- Slovenian Research Agency
- National Research, Development and Innovation Office – NKFIH
- Hungarian Academy of Sciences
Zitieren
APA
Brešar, B., Bujtás, C., Gologranc, T., Klavžar, S., Košmrlj, G., Patkós, B., Tuza, Z., & Vizer, M. (2017). Grundy dominating sequences and zero forcing sets. Discrete Optimization, 26, 66-77. https://doi.org/10.1016/j.disopt.2017.07.001
Vancouver
Brešar B, Bujtás C, Gologranc T, Klavžar S, Košmrlj G, Patkós B, et al. Grundy dominating sequences and zero forcing sets. Discrete Optimization. 2017;26:66-77. doi:10.1016/j.disopt.2017.07.001
BibTeX
@article{Brear2017,
author = {Brešar, Boštjan and Bujtás, Csilla and Gologranc, Tanja and Klavžar, Sandi and Košmrlj, Gašper and Patkós, Balázs and Tuza, Zsolt and Vizer, Máté},
title = {Grundy dominating sequences and zero forcing sets},
journal = {Discrete Optimization},
year = {2017},
volume = {26},
pages = {66--77},
doi = {10.1016/j.disopt.2017.07.001}
}
EUVIMED