EUVIMEDEUVIMED entdecken
Crossref

Grundy dominating sequences and zero forcing sets

Boštjan Brešar, Csilla Bujtás, Tanja Gologranc, Sandi Klavžar, Gašper Košmrlj, Balázs Patkós, Zsolt Tuza, Máté Vizer

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →