Bibliographic Details
| Title: |
L-STEP DOMINATION NUMBER AND ITS COMPUTATION. |
| Authors: |
Zhao, Yancai1, Xia, Peng2 |
| Source: |
Advances & Applications in Discrete Mathematics. Apr2026, Vol. 43 Issue 3, p381-399. 19p. |
| Subjects: |
Dominating set, NP-complete problems, Algorithms, Graph theory, Tree graphs |
| Abstract: |
The k-step domination problem is to find a minimum vertex set D ⊆ 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 problem, which is to find a minimum vertex set D ⊆ V of a graph G = (V, E) such that each vertex v of the graph G is either in D or at exact distance αν from some vertex of D, where αν 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 a special list L. Finally, by using a labeling method, we provide a linear time algorithm to produce an L-step dominating set of a tree. [ABSTRACT FROM AUTHOR] |
|
Copyright of Advances & Applications in Discrete Mathematics is the property of Pushpa Publishing House and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
