The identifying code number and Mycielski's construction of graphs

Document Type : Research Paper

Authors

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

Abstract

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.

Keywords

Main Subjects

References

[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)
218–222.
[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,
(2006).
Transactions on Combinatorics
Volume 11, Issue 4 - Serial Number 4
December 2022
Pages 309-316

Files

Cited by

History

  • Receive Date: 07 December 2020
  • Revise Date: 09 August 2021
  • Accept Date: 08 November 2021
  • Published Online: 01 December 2022

Share

How to cite

Statistics