Three Bounds For Identifying Code Number

Document Type : Research Paper

Authors

Department of Pure Mathematics, Faculty of Science, Imam Khomeini International University, Qazvin, Iran.

Abstract

Let G=(V,E) be a simple graph. A set C of vertices G is an identifying set of G if for every two vertices x and y belong to V the sets NG[x]∩C and NG[y]∩C are non-empty and different. Given a graph G, the smallest size of an identifying set of G is called the identifying code number of G and is denoted by γID(G). Two vertices x and y are twins when NG[x]=NG[y]. Graphs with at least two twin vertices are not identifiable graphs. In this paper,  we present three bounds for identifying code number.

Keywords

References

  1. D. Auger, Minimal identifying codes in trees and planar graphs with large girth, European J. Combin. (5) 31 (2010), 1372-84.
  2.  J. Amjadi , S. Nazari-Moghaddam , SM. Sheikholeslami, L. Volkmann, Total roman domination number of trees, Australas. J. Combin. (2) 69 (2017), 271-85.
  3.  N. Biggs, Algebraic graph theory. Cambridge university press, Cambridge, 1993.
  4.  C. Chen, C. Lu , Z. Miao, Identifying codes and locatingdominating sets on paths and cycles, Discrete Appl. Math, (15) 159 (2011), 1540-7.
  5.  F. Foucaud, E. Guerrini , M. Kovse, R. Naserasr, A. Parreau, and P. Valicov, Extremal graphs for the identifying code problem. European J. Combin. (4) 32 (2011), 628-638.
  6.  F. Foucaud , R. Klasing, A. Kosowski, A. Raspaud, On the size of identifying codes in triangle-free graphs, Discrete Appl. Math, (10-11) 160 (2012), 1532-46.
  7.  A. Frieze , R. Martin, J. Moncel, M. Ruszinke, C. Smyth, Codes identifying sets of vertices in random networks, Discrete Math. (9-10) 307 (2007), 1094-107.
  8.  S. Gravier, J. Monce, A. Semri, Identifying codes of cycles, European J. Combin. (5) 27 (2006), 767-76.
  9.  C. Godsil, GF. Royle, Algebraic graph theory, Springer Science & Business Media; 2001 Apr 20.
  10.  I. Honkala, T. Laihonen, On identifying codes in the triangular and square grids, SIAM J. Comput. (2) 33 (2004), 304-12.
  11.  MG. Karpovsky, K. Chakrabarty, LB. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inf. Theory, (2) 44 (1998),599-611.
  12.  Z. Mansouri, DA. Mojdeh, Outer independent rainbow dominating functions in graphs, Opuscula Math. (5) 40 (2020), 599-615.
  13.  F. Ramezani , ED. Rodriguez-Bazan, JA. Rodriguez-Velazquez, On the roman domination number of generalized Sierpinski graphs, Filomat, (20) 31 (2017), 6515-6528.
  14.  A. Shaminezhad , E. Vatandoost, On 2-rainbow domination number of functigraph and its complement, Opuscula Math. (5) 40 (2020), 617-627.
Journal of Algebra and Related Topics
Volume 10, Issue 2
December 2022
Pages 61-67

Files

Share

How to cite

Statistics