Algorithmic Complexity and Bounds for Domination Subdivision Numbers of Graphs

Fu-Tao Hu, Chang-Xu Zhang, Shu-Cheng Yang and Xiaogang Liu

Journal of Mathematics, 2024, vol. 2024, 1-10

Abstract: 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.

Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/jmath/2024/3795448.pdf (application/pdf)
http://downloads.hindawi.com/journals/jmath/2024/3795448.xml (application/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jjmath:3795448

DOI: 10.1155/2024/3795448

Access Statistics for this article

More articles in Journal of Mathematics from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().