Graphs with Equal Domination, Connected Domination, and Watching Numbers

Articles in Press

Document Type : Original paper

Authors

1 Faculty of Mathematical Sciences University of Guilan, P. O. Box 41335-19141, Rasht, Iran

2 Faculty of Mathematical Sciences, University of Guilan, P. O. Box 41335-19141, Rasht, Iran

3 Department of Basic Science Imam Khomeini International University, P. O. Box 34148-96818, Qazvin, Iran

Abstract

This paper investigates how the parameters $\gamma(G)$, $\beta_c(G)$, and $\omega(G)$ influence and characterize the structure of a graph.  We prove that if $G$ is of the form $H \odot K_1$, then $\gamma(G) = \beta_c(G) = \omega(G)$. Furthermore, under the assumption that $\gamma(G) = \beta_c(G) = \omega(G)$ and by leveraging properties of connected vertex covers and dominating sets, we show that $G$ belongs to a specific class of graphs.

Keywords

Main Subjects

References

1] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, Wireless sensor networks: A survey, Computer Networks 38 (2002), no. 4, 393–422. https://doi.org/10.1016/S1389-1286(01)00302-4
[2] D. Auger, I. Charon, O. Hudry, and A. Lobstein, Watching systems in graphs: An extension of identifying codes, Discrete Appl. Math. 161 (2013), no. 12, 1674–1685. https://doi.org/10.1016/j.dam.2011.04.025
[3] D. Auger, I. Charon, O. Hudry, and A. Lobstein, Maximum size of a minimum watching system and the graphs achieving the bound, Discrete Appl. Math. 164 (2014), 20–33. https://doi.org/10.1016/j.dam.2012.08.028
[4] I. Bekmezci, O.K. Sahingoz, and S¸. Temel, Flying Ad-Hoc networks (FANETs): A survey, Ad Hoc Networks 11 (2013), no. 3, 1254–1270. https://doi.org/10.1016/j.adhoc.2012.12.004
[5] M. Cardei and J. Wu, Energy-efficient connected coverage in wireless sensor networks, Int. J. Sensor Networks 3 (2006), no. 3, 179–194.
[6] N. De, Application of corona product of graphs in computing topological indices of some special chemical graphs, Handbook of Research on Applied Cybernetics and Systems Science, IGI Global, 2017, pp. 82–101. https://doi.org/10.4018/978-1-5225-2498-4.ch004
[7] J.F. Fink, M.S. Jacobson, L.F. Kinch, and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985), 287–293. https://doi.org/10.1007/BF01848079
[8] R. Frucht and F. Harary, On the corona of two graphs, Aequationes Math. 4 (1970), 322–325. https://doi.org/10.1007/BF01844162
[9] L.L. Kelleher, Domination in Graphs and its Application to Social Network Theory: A Dissertation, Northeastern University, 1985.
[10] O. Ore, Theory of Graphs, vol. 38, American Mathematical Society Colloquium Publishers, Providence, RI, 1962.
[11] M. Roozbayani and H.R. Maimani, Identifying codes and watching systems in Kneser graphs, Discrete Math. Algorithms Appl. 9 (2017), no. 1, 1750007. https://doi.org/10.1142/S1793830917500070
[12] M. Roozbayani, H.R. Maimani, and A. Tehranian, Watching systems of triangular graphs, Trans. Comb. 3 (2014), no. 1, 51–57. https://doi.org/10.22108/toc.2014.4127
[13] R. Sharma, B. Adhikari, and A. Mishra, Structural and spectral properties of corona graphs, Discrete Appl. Math. 228 (2017), 14–31. https://doi.org/10.1016/j.dam.2017.01.005
[14] S. Slijepcevic and M. Potkonjak, Power efficient organization of wireless sensor networks, IEEE International Conference on Communications (ICC 2001), vol. 2, IEEE, 2001, pp. 472–476. https://doi.org/10.1109/ICC.2001.936985
[15] J. Wu and H. Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, J. Comm. Networks 4 (2002), 59–70. https://doi.org/10.1145/313239.313261
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 10 July 2026

Files

Share

How to cite

Statistics