THE IDENTIFYING CODE NUMBER AND FUNCTIGRAPHS

Document Type : Original Manuscript

Authors

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

Abstract

Let G = (V (G); E(G)) be a simple graph. A set D of vertices G is an identifying code of G; if for every two vertices x and y the sets N_G[x] \ D and N_G[y] \ D are non- empty and different. The minimum cardinality of an identifying code in graph G is the identifying code number of G and it is denoted by gamma ID(G): Two vertices x and y are twin, when N_G[x] = N_G[y]: Graphs with at least two twin vertices are not identifiable graphs. In this paper, we deal with identifying code number of functigraph of G: Two upper bounds on identifying code number of functigraph are given. Also, we present some graph G with identifying code number |V (G)| - 2.

Keywords

References

1. A. R. Ashrafi, A. Hamzeh and S. Hossein-Zadeh, Calculation of some topological indices of splices and links of graphs, J. Appl. Math. Informatics, 29(1-2) (2011), 327–335.
2. F. Foucaud, S. Gravier, R. Naserasr, A. Parreau and P. Valicov, Identifying codes in line graphs, J. Graph Theory, 73(4) (2013), 425–448.
3. F. Foucaud, E. Guerrini, M. Kove, R. Naserasr, A. Parreau and P. Valicov, Extremal graphs for the identifying code problem, European J. Combin., 32(4) (2011), 628–638.
4. F. Foucaud, R. Klasing, A. Kosowski and A. Raspaud, On the size of identifying codes in triangle-free graphs, Discrete Appl. Math., 160(10-11) (2012), 1532– 1546.
5. F. Foucaud and G. Perarnau, Bounds for identifying codes in terms of degree parameters, Electron. J. Combin., 19(1) (2012) 32.
6. S. Gravier, J. Moncel and A. Semri, Identifying codes of cycles, European J. Combin., 27(5) (2006), 767–776.
7. T. Haynes, D. Knisley, E. Seier and Y. Zou, A quantitative analysis of secondary RNA structure using domination based parameters on trees, BMC bioinformatics, 7(1) (2006), 108.
8. O. Hudry and A. Lobstein, Unique (optimal) solutions: Complexity results for identifying and locating?dominating codes, Theoret. Comput. Sci., 767 ( 2019), 83–102.
9. 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(2) (1998), 599–611.
10. M. Laifenfeld, A. Trachtenberg, R. Cohen and D. Starobinski, Joint monitoring and routing in wireless sensor networks using robust identifying codes, Mobile
Networks and Applications, 14(4) (2009), 415–432.
11. D.F. Rall and K. Wash, Identifying codes of the direct product of two cliques, European J. Combin., 36 (2014), 159–171.
12. S. Ray, R. Ungrangsi, D. Pellegrini, A. Trachtenberg and D. Starobinski, March. Robust location detection in emergency sensor networks, In IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No. 03CH37428), 2 (2003), 1044–1053.
13. A. Sen, V.H. Goliber, C. Zhou and K. Basu, July. Terrorist Network Monitoring with Identifying Code, In International Conference on Social Computing, Behavioral-Cultural Modeling and Prediction and Behavior Representation in Modeling and Simulation (2018), 329–339.
Journal of Algebraic Systems
Volume 10, Issue 1
September 2022
Pages 155-166

Files

Share

How to cite

Statistics