Semi-total Domination in Unit Disk Graphs

Publications

Semi-total Domination in Unit Disk Graphs

Author : Ms Sasmita Rout

Year : 2024

Publisher : Springer Science and Business Media Deutschland GmbH

Source Title : Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Document Type :

Abstract

Let G= (V, E) be a simple undirected graph with no isolated vertex. A set D⊆ V is a dominating set if each vertex u∈ V is either in D or is adjacent to a vertex v∈ D. A set Dt2⊆ V is said to be a semi-total dominating set if (i) Dt2 is a dominating set, and (ii) for every vertex u∈ Dt2, there exists a vertex v∈ Dt2 such that the distance between u and v in G is within 2. Given a graph G, the semi-total domination problem is to find a semi-total dominating set of minimum cardinality. The semi-total domination problem is NP-complete for general graphs. It is also NP-complete on some special graph classes, such as planar, split, and chordal bipartite graphs. In this paper, we have shown that it is NP-complete for unit disk graphs. We propose a 6-factor approximation algorithm for the semi-total dominating set problem in unit disk graphs. The algorithm’s running time is O(nk), where n and k are the number of vertices and the size of the maximal independent set of the given UDG, respectively. In addition, we show that the minimum semi-total domination problem in a graph with maximum degree D admits a 2 + ln (D+ 1 ) -factor approximation algorithm which is an improvement over the best-known result 2 + 3 ln (D+ 1 ).