On the L-grundy domination number of a graph

Boštjan Brešar, Tanja Gologranc, Michael A. Henning, Tim Kos

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Pages (from-to)3205-3215
Number of pages11
Issue number10
Publication statusPublished - Dec 2020


  • Forests
  • Grundy total domination number
  • L-grundy domination number
  • Regular graphs
  • Split graphs

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'On the L-grundy domination number of a graph'. Together they form a unique fingerprint.

Cite this