On the watching number of graphs

Document Type : Research Article

Authors

Department of‎ ‎pure Mathematics‎, ‎Faculty of science, Imam Khomeini International University‎, ‎P.O.Box 34149-16818, Qazvin‎, ‎Iran.

Abstract

Let $G=(V‎, ‎E)$ be a simple and undirected graph‎. ‎A watcher $\omega_i$ of $G$ is a couple of $\omega_i=(v_i‎, ‎Z_i),$ where $v_i \in V$ and $Z_i$ is a subset of the closed neighborhood of $v_i.$ If a vertex $v \in Z_i,$ we say that $v$ is covered by $\omega_i.$ A set $W=\{\omega_1‎, ‎\omega_2‎, ‎\dots‎, ‎\omega_k\}$‎, ‎of watchers is a watching system for $G$ if the sets $L_W(v)=\{\omega_i~:~v \in Z_i‎ ~,~ ‎1 \le i \le k\}$ are non-empty and distinct‎, ‎for every $v \in V$‎. ‎In this paper‎, ‎we study the watching systems of some graphs‎, ‎and consider the watching number of Mycielski's construction of some graphs‎.

Keywords

Main Subjects

References

[1] A. R. Ashrafi, A. Hamzeh and S. Hossein Zadeh, Calculation of some topological indices of splices and links of graphs, J. Appl. Math. Inform. 29 (2011), no. 1-2, 327--335.
[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.
[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), part 1, 20--33.
[4] S. Balamurgan, M. Anitha and N. Anbazhagan, Various domination parameters in mycielski’s graphs, Int. J. Pure Appl. Math. 119 (2018), no. 15, 203--211.
[5] F. Foucaud, S. Gravier, R. Naserasr, A. Parreau and P. Valicov, Identifying codes in line graphs, J. Graph Theory 73 (2013), no. 4, 425--448.
[6] F. Foucaud and G. Perarnau, Bounds for identifying codes in terms of degree parameters, Electron. J. Combin. 19 (2012), no. 1, Paper 32, 28 pages.
[7] D. A. Mojdeh and N. J. Rad, On domination and its forcing in Mycielski’s graphs, Sci. Iran. 15 (2008), no. 2, 218--222.
[8] J. Mycielski, Sur le coloriage des graphes, In Colloq. Math. 3 (1955) 9 pages.
[9] D. F. Rall and K. Wash, Identifying codes of the direct product of two cliques, European J. Combin. 36 (2014), 159--171.
[10] M. Roozbayani, H. Maimani and A. Tehranian, Watching systems of triangular graphs. Trans. Comb. 3 (2014), no.1, 51--57.
[11] M. Roozbayani and H. R. Maimani, Identifying codes and watching systems in kneser graphs, Discrete Math. Algorithms Appl. 9 (2017), no. 1, 1750007, 9 pages.
[12] A. Shaminejad, E. Vatandoost and K. Mirasheh, The identifying code number and Mycielski’s construction of graphs, Trans. Comb. 11 (2022), no. 4, 309--316.
Journal of the Iranian Mathematical Society
Volume 4, Issue 2
July 2023
Pages 179-188

Files

Share

How to cite

Statistics