$L$-STEP DOMINATION NUMBER AND ITS COMPUTATION
Advances and Applications in Discrete Mathematics · 14.04.2026 · 43 (3) · 381-399
DOI: 10.17654/0974165826025 ↗Kurz gefasst
Fachartikel in der Zeitschrift Advances and Applications in Discrete Mathematics, online erschienen am 14.04.2026. Verfasst von Yancai Zhao und 1 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
The $k$-step domination problem is to find a minimum vertex set $D\subseteq V$ of a graph $G=(V, E)$ such that every vertex of the graph is either in $D$ or at exact distance $k$ from some vertex of $D$. In this paper, we extend this concept and initiate the study of $L$-step domination, which is to find a minimum vertex set $D\subseteq V$ of a graph $G=(V, E)$ such that each vertex $v$ of the graph $G$ is either in $D$ or at exact distance $a_v$ from some vertex of $D$, where $a_v$ is an arbitrary nonnegative integer assigned to $v$. We show that the $L$-step domination problem is NP-complete for many known classes of graphs. Then we compute the $L$-step domination numbers for some special classes of graphs and for some special lists $L$. Finally, by using a labeling method, we provide a linear time algorithm to produce an $L$-step dominating set of any a tree. Received: January 6, 2026Accepted: March 7, 2026
Zitieren
APA
Zhao, Y., & Xia, P. (2026). $L$-STEP DOMINATION NUMBER AND ITS COMPUTATION. Advances and Applications in Discrete Mathematics, 43(3), 381-399. https://doi.org/10.17654/0974165826025
Vancouver
Zhao Y, Xia P. $L$-STEP DOMINATION NUMBER AND ITS COMPUTATION. Advances and Applications in Discrete Mathematics. 2026;43(3):381-399. doi:10.17654/0974165826025
BibTeX
@article{Zhao2026,
author = {Zhao, Yancai and Xia, Peng},
title = {$L$-STEP DOMINATION NUMBER AND ITS COMPUTATION},
journal = {Advances and Applications in Discrete Mathematics},
year = {2026},
volume = {43},
number = {3},
pages = {381--399},
doi = {10.17654/0974165826025}
}
EUVIMED