International Journal of Nonlinear Analysis and Applications

Identifying code number of some Cayley graphs

Document Type : Research Paper

Authors

1 Department of Basic Science, Imam Khomeini International University, P. O. Box 3414896818, Qazvin, Iran

2 Department of Mathematics, Central Tehran Branch, Islamic Azad University, Tehran, Iran

Abstract

Let $\Gamma=(V, E)$ be a simple graph. A set $C$ of vertices $\Gamma$ is an identifying  set  of $\Gamma$ if for every two vertices $x$ and $y$ the sets $N_{\Gamma}[x] \cap C$ and $N_{\Gamma}[y] \cap C$ are non-empty and different. Given a graph $\Gamma,$ the smallest size of an identifying set of $\Gamma$ is called the identifying code number of $\Gamma$ and is denoted by $\gamma^{ID}(\Gamma).$ Two vertices $x$ and $y$ are twins when $N_{\Gamma}[x]=N_{\Gamma}[y].$ Graphs with at least two twin vertices are not identifiable graph. In this paper, we study identifying code number of some Cayley graphs.

Keywords

[1] D. Auger, Minimal identifying codes in trees and planar graphs with large girth, Eur. J. Combin. 31 (2010), 1372–1384.
[2] J. Amjadi, S. Nazari-Moghaddam, S. M. Sheikholeslami and L. Volkmann, Total Roman domination number of trees, Aust. J. Combin. 69 (2017), 271–285.
[3] C. Chen, C. Lu and Z. Miao, Identifying codes and locating–dominating sets on paths and cycles, Discrete Appl. Math. 159 (2011), 1540–1547.
[4] C. Camarero, C. Martınez and R. Beivide, Identifying codes of degree 4 Cayley graphs over Abelian groups, Adv. Math. Commun. 9 (2015), 129.
[5] M. Dettlaff, M. Lemanska, M. Miotk, J. Topp, R. Ziemann and P. Zylinski, Graphs with equal domination and certified domination numbers, Opuscula Math. 39 (2019), 815–827.
[6] F. Foucaud, E. Guerrini, M. Kovse, R. Naserasr, A. Parreau and P. Valicov, Extremal graphs for the identifying code problem, Eur. J. Combin. 32 (2011), 628–638.
[7] F. Foucaud, R. Klasing, A. Kosowski and A. Raspaud, On the size of identifying codes in triangle-free graphs, Discrete Appl. Math. 160 (2010), 1532–1546.
[8] A. Frieze, R. Martin, J. Moncel, M. Ruszinko and C. Smyth, Codes identifying sets of vertices in random networks, Discrete Math. 307 (2007), 1094–1107.
[9] S. Gravier, J. Moncel and A. Semri, Identifying codes of cycles, Eur. J. Combin. 27 (2006), 767–776.
[10] T. Haynes, D. Knisley, E. Seier and Y. Zou, A quantitative analysis of secondary RNA structure using domination based parameters on trees, BMC Bioinf. 7 (2006), 108.
[11] I. Honkala and T. Laihonen, On identifying codes in the triangular and square grids, SIAM J. Comput. 33 (2004), 304–312.
[12] M.G. Karpovsky, K. Chakrabarty and L.B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inf. Theory 44 (1998), 599–611.
[13] Z. Mansouri and D.A. Mojdeh, Outer independent rainbow dominating functions in graphs, Opuscula Math. 40 (2020), 599–615.
[14] R. Nikandish, O. Khani Nasab and E. Dodonge, Minimum identifying codes in some graphs differing by matching, Discrete Math. Algorithms Appl. 12 (2020), 2050046.
[15] A. Shaminezhad and E. Vatandoost, On 2-rainbow domination number of functigraph and its complement, Opuscula Math. 40 (2020), 617–627.
[16] A. Shaminezhad, E. Vatandoost and K. Mirasheh, The identifying code number and Mycielski’s construction of graphs, Trans. Combin. Articles in press, doi.org/10.22108/TOC.2021.126368.1794.
[17] E. Vatandoost and F. Ramezani, On the domination and signed domination numbers of zero-divisor graph, Electron. J. Graph Theory Appl. 4 (2016), 148–156.
International Journal of Nonlinear Analysis and Applications
Volume 13, Issue 2
July 2022
Pages 3183-3189
  • Receive Date: 10 November 2021
  • Revise Date: 20 February 2022
  • Accept Date: 19 May 2022