L-STEP DOMINATION NUMBER AND ITS COMPUTATION.
Saved in:
| 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 |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 194762762 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: L-STEP DOMINATION NUMBER AND ITS COMPUTATION. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Zhao%2C+Yancai%22">Zhao, Yancai</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Xia%2C+Peng%22">Xia, Peng</searchLink><relatesTo>2</relatesTo> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Advances+%26+Applications+in+Discrete+Mathematics%22">Advances & Applications in Discrete Mathematics</searchLink>. Apr2026, Vol. 43 Issue 3, p381-399. 19p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Dominating+set%22">Dominating set</searchLink><br /><searchLink fieldCode="DE" term="%22NP-complete+problems%22">NP-complete problems</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+theory%22">Graph theory</searchLink><br /><searchLink fieldCode="DE" term="%22Tree+graphs%22">Tree graphs</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=194762762 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.17654/0974165826025 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 19 StartPage: 381 Subjects: – SubjectFull: Dominating set Type: general – SubjectFull: NP-complete problems Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Graph theory Type: general – SubjectFull: Tree graphs Type: general Titles: – TitleFull: L-STEP DOMINATION NUMBER AND ITS COMPUTATION. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Zhao, Yancai – PersonEntity: Name: NameFull: Xia, Peng IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 04 Text: Apr2026 Type: published Y: 2026 Identifiers: – Type: issn-print Value: 09741658 Numbering: – Type: volume Value: 43 – Type: issue Value: 3 Titles: – TitleFull: Advances & Applications in Discrete Mathematics Type: main |
| ResultId | 1 |
