Grundy dominating sequences and zero forcing sets
  • Metaadatok
Tartalom: http://real.mtak.hu/62815/
Archívum: MTA Könyvtár
Gyűjtemény: Status = In Press
Type = Article
Cím:
Grundy dominating sequences and zero forcing sets
Létrehozó:
Bresar, Bostjan
Bujtás, Csilla
Gologranc, Tanja
Klavzar, Sandi
Kosmrlj, Gasper
Patkós, Balázs
Tuza, Zsolt
Vizer, Máté
Kiadó:
Elsevier
Dátum:
2017
Téma:
QA166-QA166.245 Graphs theory / gráfelmélet
Tartalmi leírás:
In a graph $G$ a sequence $v_1,v_2,dots,v_m$ of vertices is Grundy
dominating if for all $2le i le m$ we have $N[v_i]notsubseteq
cup_(j=1)^(i-1)N[v_j]$ and is Grundy total dominating if for all
$2le i le m$ we have $N(v_i)notsubseteq cup_(j=1)^(i-1)N(v_j)$.
The length of the longest Grundy (total) dominating sequence has
been studied by several authors. In this paper we introduce two
similar concepts when the requirement on the neighborhoods is
changed to $N(v_i)notsubseteq cup_(j=1)^(i-1)N[v_j]$ or
$N[v_i]notsubseteq cup_(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.
Nyelv:
magyar
Típus:
Article
PeerReviewed
info:eu-repo/semantics/article
Formátum:
text
Azonosító:
Bresar, Bostjan and Bujtás, Csilla and Gologranc, Tanja and Klavzar, Sandi and Kosmrlj, Gasper and Patkós, Balázs and Tuza, Zsolt and Vizer, Máté (2017) Grundy dominating sequences and zero forcing sets. Discrete Optimization. ISSN 1572-5286 (In Press)
Kapcsolat:
https://doi.org/10.1016/j.disopt.2017.07.001