Algorithmic Complexity and Bounds for Domination Subdivision Numbers of Graphs
Let G=V,E be a simple graph. A subset D⊆V is a dominating set if every vertex not in D is adjacent to a vertex in D. The domination number of G, denoted by γG, is the smallest cardinality of a dominating set of G. The domination subdivision number sdγG of G is the minimum number of edges that must b...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2024-01-01
|
| Series: | Journal of Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2024/3795448 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832553042687295488 |
|---|---|
| author | Fu-Tao Hu Chang-Xu Zhang Shu-Cheng Yang |
| author_facet | Fu-Tao Hu Chang-Xu Zhang Shu-Cheng Yang |
| author_sort | Fu-Tao Hu |
| collection | DOAJ |
| description | Let G=V,E be a simple graph. A subset D⊆V is a dominating set if every vertex not in D is adjacent to a vertex in D. The domination number of G, denoted by γG, is the smallest cardinality of a dominating set of G. The domination subdivision number sdγG of G is the minimum number of edges that must be subdivided (each edge can be subdivided at most once) in order to increase the domination number. In 2000, Haynes et al. showed that sdγG≤dGv+dGv−1 for any edge uv∈EG with dGu≥2 and dGv≥2 where G is a connected graph with order no less than 3. In this paper, we improve the above bound to sdγG≤dGu+dGv−NGu∩NGv−1, and furthermore, we show the decision problem for determining whether sdγG=1 is NP-hard. Moreover, we show some bounds or exact values for domination subdivision numbers of some graphs. |
| format | Article |
| id | doaj-art-29066f824ef64db5b587c06c537a1b98 |
| institution | Kabale University |
| issn | 2314-4785 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Mathematics |
| spelling | doaj-art-29066f824ef64db5b587c06c537a1b982025-02-03T05:57:02ZengWileyJournal of Mathematics2314-47852024-01-01202410.1155/2024/3795448Algorithmic Complexity and Bounds for Domination Subdivision Numbers of GraphsFu-Tao Hu0Chang-Xu Zhang1Shu-Cheng Yang2School of Mathematical SciencesSchool of Mathematical SciencesSchool of Mathematical SciencesLet G=V,E be a simple graph. A subset D⊆V is a dominating set if every vertex not in D is adjacent to a vertex in D. The domination number of G, denoted by γG, is the smallest cardinality of a dominating set of G. The domination subdivision number sdγG of G is the minimum number of edges that must be subdivided (each edge can be subdivided at most once) in order to increase the domination number. In 2000, Haynes et al. showed that sdγG≤dGv+dGv−1 for any edge uv∈EG with dGu≥2 and dGv≥2 where G is a connected graph with order no less than 3. In this paper, we improve the above bound to sdγG≤dGu+dGv−NGu∩NGv−1, and furthermore, we show the decision problem for determining whether sdγG=1 is NP-hard. Moreover, we show some bounds or exact values for domination subdivision numbers of some graphs.http://dx.doi.org/10.1155/2024/3795448 |
| spellingShingle | Fu-Tao Hu Chang-Xu Zhang Shu-Cheng Yang Algorithmic Complexity and Bounds for Domination Subdivision Numbers of Graphs Journal of Mathematics |
| title | Algorithmic Complexity and Bounds for Domination Subdivision Numbers of Graphs |
| title_full | Algorithmic Complexity and Bounds for Domination Subdivision Numbers of Graphs |
| title_fullStr | Algorithmic Complexity and Bounds for Domination Subdivision Numbers of Graphs |
| title_full_unstemmed | Algorithmic Complexity and Bounds for Domination Subdivision Numbers of Graphs |
| title_short | Algorithmic Complexity and Bounds for Domination Subdivision Numbers of Graphs |
| title_sort | algorithmic complexity and bounds for domination subdivision numbers of graphs |
| url | http://dx.doi.org/10.1155/2024/3795448 |
| work_keys_str_mv | AT futaohu algorithmiccomplexityandboundsfordominationsubdivisionnumbersofgraphs AT changxuzhang algorithmiccomplexityandboundsfordominationsubdivisionnumbersofgraphs AT shuchengyang algorithmiccomplexityandboundsfordominationsubdivisionnumbersofgraphs |