Geodesic
On the L-grundy domination number of a graph
Filomat, Tome 34 (2020) no. 10, p. 3205

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

DOI

In this paper, we continue the study of the L-Grundy domination number of a graph introduced and first studied in [Grundy dominating sequences and zero forcing sets, Discrete Optim. 26 (2017) 66–77]. A vertex in a graph dominates itself and all vertices adjacent to it, while a vertex totally dominates another vertex if they are adjacent. A sequence of distinct vertices in a graph G is called an L-sequence if every vertex v in the sequence is such that v dominates at least one vertex that is not totally dominated by any vertex that precedes v in the sequence. The maximum length of such a sequence is called the L-Grundy domination number, γ L gr (G), of G. We show that the L-Grundy domination number of every forest G on n vertices equals n, and we provide a linear-time algorithm to find an L-sequence of length n in G. We prove that the decision problem to determine if the L-Grundy domination number of a split graph G is at least k for a given integer k is NP-complete. We establish a lower bound on γ L gr (G) when G is a regular graph, and investigate graphs G on n vertices for which γ L gr (G) = n.
DOI : 10.2298/FIL2010205B
Classification : 05C69, 05C65, 05C85
Keywords: Grundy total domination number, L-Grundy domination number, Forests, Split graphs, Regular graphs 
Boštjan Brešar; Tanja Gologranc; Michael A Henning; Tim Kos. On the L-grundy domination number of a graph. Filomat, Tome 34 (2020) no. 10, p. 3205 . doi: 10.2298/FIL2010205B
@article{10_2298_FIL2010205B,
     author = {Bo\v{s}tjan Bre\v{s}ar and Tanja Gologranc and Michael A Henning and Tim Kos},
     title = {On the {L-grundy} domination number of a graph},
     journal = {Filomat},
     pages = {3205 },
     year = {2020},
     volume = {34},
     number = {10},
     doi = {10.2298/FIL2010205B},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.2298/FIL2010205B/}
}
TY  - JOUR
AU  - Boštjan Brešar
AU  - Tanja Gologranc
AU  - Michael A Henning
AU  - Tim Kos
TI  - On the L-grundy domination number of a graph
JO  - Filomat
PY  - 2020
SP  - 3205 
VL  - 34
IS  - 10
UR  - http://geodesic.mathdoc.fr/articles/10.2298/FIL2010205B/
DO  - 10.2298/FIL2010205B
LA  - en
ID  - 10_2298_FIL2010205B
ER  - 
%0 Journal Article
%A Boštjan Brešar
%A Tanja Gologranc
%A Michael A Henning
%A Tim Kos
%T On the L-grundy domination number of a graph
%J Filomat
%D 2020
%P 3205 
%V 34
%N 10
%U http://geodesic.mathdoc.fr/articles/10.2298/FIL2010205B/
%R 10.2298/FIL2010205B
%G en
%F 10_2298_FIL2010205B

Cité par Sources :