Identifying code number of non-commuting graph of a group

Articles in Press

Document Type : Research Paper

Authors

Department of Mathematics, Faculty of Basic Science, Imam Khomeini International University, P. O. Box 34148-96818, Qazvin, Iran.

Abstract

Let $G$ be a finite non-abelian group with center $Z(G)$. The non-commuting graph of $G$, denoted by $\Gamma_G$, is the graph whose vertex set is $G \setminus Z(G)$, where two distinct vertices $x$ and $y$ are adjacent whenever $xy \neq yx$. For a graph $\Gamma$, a subset $C \subseteq V(\Gamma)$ is called an identifying code if, for every pair of distinct vertices $x$ and $y$, the sets $N_{\Gamma}[x]\cap C$ and $N_{\Gamma}[y]\cap C$ are nonempty and distinct. The minimum cardinality of an identifying code in $\Gamma$ is called the identifying code number and is denoted by $\gamma^{ID}(\Gamma)$. In this paper, we investigate the identifiability of non-commuting graphs associated with groups. Furthermore, for several classes of finite non-abelian groups, we determine the identifying code number of their non-commuting graphs.

Keywords

Main Subjects

References

[1] A.Abdollahi, S. Akbari and H. R. Maimani, Non-commuting graph of a group, J. Algebra, 298 No. 2 (2006) 468-492.
[2] S. Ahmadi, E. Vatandoost and A. Behtoei, Domination number and identifying code number of the subdivision graphs, J. Algebr. Syst., 13 No. 2 (2025) 1-11.
[3] S. Ahmadi, E. Vatandoost and A. Behtoei, Identifying code number of some Cayley graphs, Int. J. Nonlinear Anal. Appl., 13 No. 2 (2022) 3183-3189.
[4] A. Akbari and A. Mohammadian, On the zero-diviser graph of a commutative ring, J. Algebra, 274 No.2 (2004) 847-855.
[5] E. A. Bertram, Some applications of graph theory to finite groups, Discrete Math., 44 (1983) 31-43.
[6] C. Chen, C. Lu and Z. Miao, Identifying codes and locating–dominating sets on paths and cycles, Discret. Appl. Math., 159 (2011) 1540-1547.
[7] F. Foucaud and E. Guerrini, Extremal graphs for the identifying code problem, Eur. J. Comb., 32 No. 4 (2011) 628-638.
[8] S. Freedman, The non-commuting, non-generating graph of a finite simple group, Q. J. Math., 76 (2025) 313-335.
[9] M. Ghorbani, Z. Gharavi and A. Zaeem-Bashi, On the eigenvalues of non-commuting graphs, Alg. Struc. Appl., 4 No. 2 (2017) 27-38.
[10] S. Gravier, J. Moncel and A. Semri, Identifying codes of cycles, Eur. J. Comb., 27 (2006) 767-776.
[11] I. N. Herstein, Abstract Algebra, Third edition, University of Chicago, 1995.
[12] M. G. Karpovsky, K. Chakrabarty and L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inf., 44 (1998) 599-611.
[13] K. Mirasheh, A. Abbasi and E. Vatandoost, Domination number and watching number of subdivision construction of graphs, Facta Universitatis, (NIS)., 40 No. 1 (2025) 33-43.
[14] B. H. Neumann, A problem of Paul Erdös on groups, J. Aust. Math. Soc. Ser. A., 21 (1976) 467-472.
[15] E. Rezaie, K. Ahmadidelir and A. Tehranian, Commutativity degree and non-commuting graph in finite groups and Mofang Loops and their relationships, Alg. Struc. Appl., 7 No. 1 (2020) 69-82.
[16] A. Shaminejad, E. Vatandoost, The identifying code number and functigraphs, J. Algebr. Syst., 10 No. 1 (2022) 155-166.
[17] A. Shaminezhad and E. Vatandoost, On 2-rainbow domination number of functigraph and its complement, Opusc. Math., 40 (2020) 617- 627.
[18] E. Vatandoost and M. Khalili, Domination number of the non-commuting graph of finite groups, Electron. J. Graph Theory Appl., 6 No. 2 (2018) 228-237.
[19] E. Vatandoost and K. Mirasheh, Three bounds for identifying code number, J. Algebra Relat. Top., 10 No. 2 (2022) 61-67.
Algebraic Structures and Their Applications

Articles in Press, Corrected Proof
Available Online from 21 October 2026

Files

Share

How to cite

Statistics