EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

$L$-STEP DOMINATION NUMBER AND ITS COMPUTATION

Yancai Zhao, Peng Xia

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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