Journal of the Iranian Mathematical Society

Journal of the Iranian Mathematical Society

Identifying code number of some of the middle graphs

Document Type : Research Article

Authors
H. Nadimi Dafrazi 1
E. Vatandoost 2
1 Department of Mathematics, Faculty of Science, Imam Khomeini International University, P.O. Box 34148-96818, Qazvin, Iran.
2 Department of Mathematics‎, ‎Faculty of Science, Imam Khomeini International University‎, ‎P‎.O‎. ‎Box 3414896818‎, ‎Qazvin‎, ‎Iran.
10.30504/jims.2026.538124.1271
Abstract
Let $G=(V‎, ‎E)$ be a simple graph‎. ‎A subset $C$ of vertices of $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 distinct and non-empty‎. ‎Given a graph $G,$ the smallest size of an identifying code of $G$ is called the identifying code number of $G$ and is denoted by $\gamma^{ID}(G).$ In this paper‎, ‎we show that for every graph $G,$ the middle graph of $G$ is an identifiable graph‎. ‎We prove that the identifying code number of the middle graph of $G$ is at most $|V(G)|$‎. ‎Also‎, ‎we determine the identifying code number of the middle graph of some graphs‎. ‎In particular‎, ‎we determine the identifying code number of the middle graph of a bipartite graph‎.
Keywords
Bipartite graph
Corona product
identifying code number
middle graph
Subjects
[1] S. Ahmadi, E. Vatandoost and A. Behtoei, Domination number and identifying code number of the subdivision graphs, J. Algebr. Syst. 13 (2025), no. 2, 1–11.
[2] D. Auger, Minimal identifying codes in trees and planar graphs with large girth, European J. Combin. 31 (2010), no. 5, 1372–1384.
[3] C. Chen, C. Lu and Z. Miao, Identifying codes and locating-dominating sets on paths and cycles, Discrete Appl. Math. 159 (2011), no. 15, 1540–1547.
[4] S. Gravier, J. Moncel and A. Semri, Identifying codes of cycles, European J. Combin. 27 (2006), no. 5, 767–776.
[5] T. Hamada and I. Yoshimura, Traversability and connectivity of the middle graph of a graph, Discrete Math. 14 (1976), no. 3, 247–255.
[6] T. Haynes, D. Knisley, E. Seier and Y. Zou, A quantitative analysis of secondary RNA structure using dominationbased parameters on trees, BMC bioinform. 7 (2006) 108–115.
[7] I. Honkala and T. Laihonen, On identifying codes in the triangular and square grids, SIAM J. Comput. 33 (2004), no. 2, 304–312.
[8] M. G. Karpovsky, K. Chakrabarty and L. B. Levitin, On a new class of codes for identifying vertices in graphs, EEE Trans. Inform. Theory 44 (1998), no. 2, 599–611.
[9] F. Kazemnejad, B. Pahlavsay, E. Palezzato and M. Torielli, Domination number of middle graphs, Trans. Comb. 12 (2023), no. 2, 79–91.
[10] K. Mirasheh, A. Abbasi and E. Vatandoost, Domination number and watching number of subdivision construction of graphs, Facta Univ. Ser. Math. Inform. 40 (2025), no. 1, 33–43.
[11] R. Yarke Salkhori, E. Vatandoost and A. Behtoei, 2-Rainbow Domination Number of the Subdivision of Graphs, Commun. Comb. Optim. 11 (2026), no. 1, 33–43.
[12] A. Shaminejad, E. Vatandoost, The identifying code number and functigraphs, J. Algebr. Syst. 10 (2022), no. 1, 155–166.
[13] E. Vatandoost and K. Mirasheh, Three bounds for identifying code number, J. Algebra Relat. Topics 10 (2022), no. 2, 61–67.
Journal of the Iranian Mathematical Society
Volume 7, Issue 1
This issue is in progress but all papers are fully citable
February 2026
Pages 25-34