The identifying code number and Mycielski's construction of graphs

Document Type : Research Paper


Department of Mathematics, Imam Khomeini International University of Qazvin, P.O.Box 3414896818, Qazvin, Iran


Let $G=(V, E)$ be a simple graph. A set $C$ of vertices $G$ is an identifying code of $G$ if for every two vertices $x$ and $y$ the sets $N_{G} [x] \cap C$ and $N_{G} [y] \cap C$ are non-empty and different. Given a graph $G,$ the smallest size of an identifying code of $G$ is called the identifying code number of $G$ and denoted by $\gamma^{ID}(G).$ Two vertices $x$ and $y$ are twins when $N_{G}[x]=N_{G}[y].$ Graphs with at least two twin vertices are not an identifiable graph. In this paper, we deal with the identifying code number of Mycielski's construction of graph $G.$ We prove that the Mycielski's construction of every graph $G$ of order $n \geq 2,$ is an identifiable graph. Also, we present two upper bounds for the identifying code number of Mycielski's construction $G,$ such that these two bounds are sharp. Finally, we show that Foucaud et al.'s conjecture is holding for Mycielski's construction of some graphs.


Main Subjects

[1] D. Auger, Minimal identifying codes in trees and planar graphs with large girth, European J. Combin., 31 no. 5
(2010) 1372–1384.
[2] C. Chen, C. Lu and Z. Miao, Identifying codes and locating-dominating sets on paths and cycles, Discrete Appl. Math.,
159 no. 15 (2011) 1540–1547.
[3] N. Fazlollahi, D. Starobinski and A. Trachtenberg, Connected identifying codes for sensor network monitoring, In 2011
IEEE Wireless Communications and Networking Conference, (2011) 1026–1031.
[4] F. Foucaud, E. Guerrini, M. Kovše, R. Naserasr, A. Parreau and P. Valicov, Extremal graphs for the identifying code
problem, European J. Combin., 32 no. 4 (2011) 628–638.
[5] F. Foucaud, R. Klasing, A. Kosowski and A. Raspaud, On the size of identifying codes in triangle-free graphs, Discrete
Appl. Math., 160 no. 10-11 (2010) 1532–1546.
[6] A. Frieze, R. Martin, J. Moncel, M. Ruszinkó and C. Smyth, Codes identifying sets of vertices in random networks,
Discrete Math., 307 no. 9-10 (2007) 1094–1107.
[7] A. N. Ghameshlou, A. Shaminezhad, E. Vatandoost and A. Khodkar, Signed domination and Mycielski’s structure in
graphs, RAIRO Oper. Res., 54 no. 4 (2020) 1077–1086.
[8] S. Gravier, J. Moncel and A. Semri, Identifying codes of cycles, European J. Combin., 27 no. 5 (2006) 767–776.
[9] I. Honkala and T. Laihonen, On identifying codes in the triangular and square grids, SIAM J. Comput., 33 no. 2
(2004) 304–312.
[10] M. G. Karpovsky, K. Chakrabarty and L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE
Trans. Inform. Theory, 44 no. 2 (1998) 599–611.
[11] A. P. Kazemi, k-tuple total domination and Mycieleskian graphs, Trans. Comb., 1 no. 1 (2010) 7–13.
[12] D. A. Mojdeh and N. Jafari Rad, On domination and its forcing in Mycielski’s graphs, Sci. Iran., 15 no. 2 (2008)
[13] J. Myscielski, Sur le coloriage des graphes, Colloq. Math., 3 (1955) 161–162.
[14] K. Thulasiraman, M. Xu, Y. Xiao and X. D. Hu, Vertex identifying codes for fault isolation in communication networks,
In Proceedings of the International Conference on Discrete Mathematics and Applications (ICDM 2006), Bangalore,