Total Roman Domination and Total Domination in Unit Disk Graphs

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, IIT Guwahati

2 Department of Computer Science and Engineering, IIIT Guwahati, Assam, India

Abstract

Let $G=(V,E)$ be a simple, undirected and connected graph. A Roman dominating function (RDF) on the graph $G$ is a function $f:V\rightarrow\{0,1,2\}$ such that each vertex $v\in V$ with $f(v)=0$ is adjacent to at least one vertex $u\in V$ with $f(u)=2$. A total Roman dominating function (TRDF) of $G$ is a function $f:V\rightarrow\{0,1,2\}$ such that $(i)$ it is a Roman dominating function, and  $(ii)$ the vertices with non-zero weights induce a subgraph with no isolated vertex. The total Roman dominating set (TRDS) problem is to minimize the associated weight, $f(V)=\sum_{u\in V} f(u)$, called the total Roman domination number ($\gamma_{tR}(G)$). Similarly, a subset $S\subseteq V$ is said to be a total dominating set (TDS) on the graph $G$ if $(i)$ $S$ is a dominating set of $G$, and $(ii)$  the induced subgraph $G[S]$ does not have any isolated vertex. The objective of the TDS problem is to minimize the cardinality of the TDS of a given graph. The TDS problem is NP-complete for general graphs.  In this paper, we propose a simple $10.5\operatorname{-}$factor approximation algorithm for TRDS problem in UDGs. The running time of the proposed algorithm is $O(|V|\log k)$, where $k$ is the number of vertices with weights $2$. It is an improvement over the best-known $12$-factor approximation algorithm with running time $O(|V|\log k)$ available in the literature. Next, we propose another algorithm for the TDS problem in UDGs, which improves the previously best-known approximation factor from $8$ to $7.79$. The running time of the proposed algorithm is $O(|V|+|E|)$.

Keywords

Main Subjects

References

[1] H.A. Ahangar, M.A. Henning, V. Samodivkin, and I.G. Yero, Total Roman domination in graphs, Appl. Anal. Discret. Math. 10 (2016), no. 2, 501–517.
http://doi.org/10.2298/AADM160802017A
[2] J. Amjadi, S. Nazari-Moghaddam, S.M. Sheikholeslami, and L. Volkmann, Total Roman domination number of trees, Australas. J. Comb. 69 (2017), no. 2, 271–285.
[3] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
https://doi.org/10.1016/j.dam.2016.03.017
[4] P. Chakradhar and P.V.S. Reddy, Algorithmic aspects of total Roman $\{2\}$-domination in graphs, Commun. Comb. Optim 7 (2022), no. 2, 183–192.
https://doi.org/10.22049/cco.2021.27063.1189
[5] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination, Structures of Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, 2021, pp. 273–307.
[6] B.N. Clark, C.J. Colbourn, and D.S. Johnson, Unit disk graphs, Discrete Math. 86 (1990), no. 1-3, 165–177.
https://doi.org/10.1016/0012-365X(90)90358-O
[7] E.J. Cockayne, R.M. Dawes, and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980), no. 3, 211–219.
https://doi.org/10.1002/net.3230100304
[8] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1–3, 11–22.
https://doi.org/10.1016/j.disc.2003.06.004
[9] O. Favaron, H. Karami, R. Khoeilar, and S.M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math. 309 (2009), no. 10, 3447–3451.
https://doi.org/10.1016/j.disc.2008.09.043
[10] G. Hao, L. Volkmann, and D.A. Mojdeh, Total double Roman domination in graphs, Commun. Comb. Optim. 5 (2020), no. 1, 27–39.
https://doi.org/10.22049/cco.2019.26484.1118
[11] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, CRC press, 1998.
[12] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Topics in Domination in Graphs, Springer, 2020.
[13] S.T. Hedetniemi and R.C. Laskar, Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete Math. 86 (1990), no. 1-3, 257–277.
https://doi.org/10.1016/0012-365X(90)90365-O
[14] M.A. Henning, A survey of selected recent results on total domination in graphs, Discrete Math. 309 (2009), no. 1, 32–63.
https://doi.org/10.1016/j.disc.2007.12.044
[15] M.A. Henning and A. Yeo, Total Domination in Graphs, Springer, 2013.
[16] C.H. Liu and G.J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013), no. 3, 608–619.
https://doi.org/10.1007/s10878-012-9482-y
[17] M.V. Marathe, H. Breu, H.B. Hunt III, S.S. Ravi, and D.J. Rosenkrantz, Simple heuristics for unit disk graphs, Networks 25 (1995), no. 2, 59–68.
https://doi.org/10.1002/net.3230250205
[18] A.C. Martinez, S. Cabrera Garcia, and A. Carrion Garcia, Further results on the total Roman domination in graphs, Mathematics 8 (2020), no. 3, Article ID: 349.
https://doi.org/10.3390/math8030349
[19] A. Poureidi, Total Roman domination for proper interval graphs, Electron. J. Graph Theory Appl. 8 (2020), no. 2, 401–413.
https://dx.doi.org/10.5614/ejgta.2020.8.2.16
[20] A. Poureidi and J. Fathali, Algorithmic complexity of triple Roman dominating functions on graphs, Commun. Comb. Optim. 9 (2024), no. 2, 217–232.
https://doi.org/10.22049/cco.2023.27884.1385
[21] K.J. Sangram and K.D. Gautam, Total Domination in Geometric Unit Disk Graphs, Proceedings of the 33rd Canadian Conference on Computational Geometry, 2021, August 10-12, 2021, 2021, pp. 219–227.
[22] W. Shang, X. Wang, and X. Hu, Roman domination and its variants in unit disk graphs, Discrete Math. Algorithms Appl. 2 (2010), no. 1, 99–105.
https://doi.org/10.1142/S1793830910000504
[23] Z. Shao, J. Amjadi, S.M. Sheikholeslami, and M. Valinavaz, On the total double roman domination, IEEE Access 7 (2019), 52035–52041.
https://doi.org/10.1109/ACCESS.2019.2911659
[24] I. Stewart, Defend the Roman empire!, Sci. Am. 281 (1999), no. 6, 136–138.
[25] P.J. Wan, K.M. Alzoubi, and O. Frieder, Distributed construction of connected dominating set in wireless ad hoc networks, Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3,
IEEE, 2002, pp. 1597–1604.
https://doi.org/10.1109/INFCOM.2002.1019411.
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 05 February 2024

Files

Share

How to cite

Statistics