A study on strong and geodetic domination integrity sets in graphs

Articles in Press

Document Type : Original paper

Authors

1 Institute of Computing Science and Technology, Guangzhou University, Guangzhou, 510006, China

2 Huangpu Research School of Guangzhou University, Guangzhou, China

3 Department of Mathematics, Sri Sivasubramaniya Nadar College of Engineering, OMR, Chennai, Tamilnadu, India

4 Department of Mathematics, St. Joseph’s Institute of Technology, OMR, Chennai, Tamilnadu, India

Abstract

Consider a graph Ω=(V,E) that is simple‎, ‎and let ϑ1 and ϑ2 be elements of V(Ω) suth that ϑ1ϑ2∈E(Ω)‎. ‎Then‎, ‎ϑ1 is said to strongly dominate ϑ2 if deg(ϑ1)≥deg(ϑ2)‎. ‎A set K of V(Ω) is identified as a strong dominating set (sd-set) if every vertex ϑ2 outside of K is strongly dominated by at least one node ϑ1 within K‎. ‎The concept of strong domination integrity for Ω is defined as SDI~(Ω)=minK⊆V⁡{|K|‎+‎m(Ω‎−‎K)‎:‎K is a sd-set of Ω\}‎. ‎Similarly‎, ‎the set K⊆V(Ω) is identified as a geodetic dominating set (gd-set) if K is both geodetic and dominating set‎. ‎The geodetic domination integrity of Ω is defined as GDI~(Ω)=min{|K|‎+‎m(Ω‎−‎K)‎:‎K is a gd-set of Ω}‎. ‎This paper delves into the study of strong and geodetic domination integrity sets‎, ‎as well as the impact of node removal on these sets‎. ‎Additionally‎, ‎it introduces the concepts of SDI~-Excellent and GDI~-Excellent graphs‎, ‎provides examples‎, ‎and derives theorems from these graphs.

Keywords

Main Subjects

References

[1] M. Atici, On the edge geodetic number of a graph, Int. J. Comput. Math. 80 (2003), no. 7, 853–861. https://doi.org/10.1080/0020716031000103376
[2] K.S. Bagga, L.W. Beineke, M.J. Lipman, and R.E. Pippert, On the edge-integrity of graphs, Congr. Numer. 60 (1987), 141–144.
[3] G. Balaraman, S.S. Kumar, and R. Sundareswaran, Geodetic domination integrity in graphs, TWMS J. App. and Eng. Math. 11 (2021), 258–267.
[4] C.A. Barefoot, R. Entringer, and H.C. Swart, Vulnerability in graphs-a comparative survey, J. Combin. Math. Combin. Comput. 1 (1987), 13–22.
[5] D. Bauer, H. Broersma, and E. Schmeichel, Toughness in graphs–a survey, Graphs Combin. 22 (2006), no. 1, 1–35. https://doi.org/10.1007/s00373-006-0649-0
[6] F. Buckley, F. Harary, and L.V. Quintas, Extremal results on the geodetic number of a graph, Scientia A 2 (1988), 17–26.
[7] G. Chartrand, F. Harary, and P. Zhang, Geodetic sets in graphs, Discuss. Math. Graph Theory 20 (2000), no. 1, 129–138.
[8] G. Chartrand, F. Harary, and P. Zhang, On the geodetic number of a graph, Networks 39 (2002), no. 1, 1–6.  https://doi.org/10.1002/net.10007
[9] S.R. Chellathurai and S.P. Vijaya, The geodetic domination number for the product of graphs, Trans. Comb. 3 (2014), no. 4, 19–30.  https://doi.org/10.22108/toc.2014.5750
[10] V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973), no. 3, 215–228. https://doi.org/10.1016/0012-365X(73)90138-6
[11] L.H. Clark, R.C. Entringer, and M.R. Fellows, Computational complexity of integrity, J. Combin. Math. Combin. Comput. 2 (1987), 179–191.
[12] E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), no. 3, 247–261. https://doi.org/10.1002/net.3230070305
[13] M.B. Cozzens, D. Moazzami, and S. Stueckle, The tenacity of the harary graphs, J. Combin. Math. Combin. Comput. 16 (1994), 33–56.
[14] M.B. Cozzens, D. Moazzami, and S. Stueckle, The tenacity of a graph.,graph theory, Combinatorics and Algorithms
(Y. Alavi and A. Schwenk, eds.), Wiley, Newyork, 1995, pp. 1111–1112.
[15] B. Ganesan, S. Raman, S. Marayanagaraj, and S. Broumi, Geodetic domination integrity in fuzzy graphs, J. Intell. Fuzzy Syst. 45 (2023), no. 2, 2209–2222.  https://doi.org/10.3233/JIFS–223249
[16] B. Ganesan, S. Raman, and M. Pal, Strong domination integrity in graphs and  fuzzy graphs, J. Intell. Fuzzy Syst. 43 (2022), no. 3, 2619–2632.  https://doi.org/10.3233/JIFS-213189
[17] F. Harary, E. Loukakis, and C. Tsouros, The geodetic number of a graph, Math. Comput. Model. 17 (1993), no. 11, 89–95.  https://doi.org/10.1016/0895-7177(93)90259-2
[18] G. Harisaran, G. Shiva, R. Sundareswaran, and M. Shanmugapriya, Connected domination integrity in graphs, Indian Journal of Natural Sciences 12 (2021),  no. 65, 30271–30276.
[19] J.H. Hattingh and M.A. Henning, On strong domination in graphs, J. Combin. Math. Combin. Comput. 26 (1998), 73–92.
[20] J.H. Hattingh and R.C. Laskar, On weak domination in graphs, Ars Combin. 49 (1998).
[21] H.A. Jung, On a class of posets and the corresponding comparability graphs, J. Combin. Theory Ser. B 24 (1978), no. 2, 125–133.  https://doi.org/10.1016/0095-8956(78)90013-8
[22] A. Kirlangic, On the weak-integrity of trees, Turkish J. Math. 27 (2003), no. 3, 375–388.
[23] F. Li and X. Li, Computing the rupture degrees of graphs, 7th International Symposium on Parallel Architectures, Algorithms and Networks, 2004. Proceedings., IEEE, 2004, pp. 368–373 https://doi.org/10.1109/ISPAN.2004.1300507
[24] Y. Li, S. Zhang, and X. Li, Rupture degree of graphs, Int. J. Comput. Math. 82 (2005), no. 7, 793–803. https://doi.org/10.1080/00207160412331336062
[25] R.E. Mariano and S.R. Canoy Jr, Edge geodetic covers in graphs, Int. Math. Forum. 4 (2009), no. 46, 2301–2310.
[26] O. Ore, Theory of graphs, American Mathematical Society Colloquium Publications 38 (1962), 206–212.
[27] D. Rautenbach, Bounds on the strong domination number, Discrete Math. 215 (2000), no. 1-3, 201–212. https://doi.org/10.1016/S0012-365X(99)00248-4
[28] E. Sampathkumar and L.P. Latha, Strong weak domination and domination balance in a graph, Discrete Math. 161 (1996), no. 1-3, 235–242.  https://doi.org/10.1016/0012-365X(95)00231-K
[29] E. Sampathkumar and H.B. Walikar, The connected domination number of a graph, J. Math. Phy. Sci. 13 (1979), no. 6, 607–613.
[30] A.P. Santhakumaran and J. John, Edge geodetic number of a graph, J. Discrete Math. Sci. Cryptogr. 10 (2007), no. 3, 415–432.  https://doi.org/10.1080/09720529.2007.10698129
[31] A. Somasundaram, Domination in fuzzy graphs–II, J. Fuzzy Math. 13 (2005), no. 2, 281–288.
[32] A. Somasundaram and S. Somasundaram, Domination in fuzzy graphs–I, Pattern Recognit. Lett. 19 (1998), no. 9, 787–791.  https://doi.org/10.1016/S0167-8655(98)00064-6
[33] R. Sundareswaran and V. Swaminathan, Domination integrity in graphs, Proceedings of International Conference on Mathematical and Experimental Physics 3 (2009), no. 8, 46–57.
[34] R. Sundareswaran and V. Swaminathan, Domination integrity of middle graphs, algebra, graph theory and their
applications, Graph Theory and Their Applications (T. Chelvam, S. Somasundaram, and R. Kala, eds.), Narosa Publishing House, New Delhi, 2010, pp. 88–92.
[35] Y. Talebi and H. Rashmanlou, New concepts of domination sets in vague graphs with applications, Int. J. Comput. Sci. Math. 10 (2019), no. 4, 375–389.  https://doi.org/10.1504/IJCSM.2019.102686
[36] Y. Talebiy and H. Rashmanlouz, Application of dominating sets in vague graphs, Appl. Math. E-Notes 17 (2017), 251–267.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 25 March 2025

Files

Share

How to cite

Statistics