Identifying Code of Some Special Graphs

Enrico Limbo Enriquez, Jesus L. Ranara, Carmelita N. Loquias, Grace M. Estrada, Teodora J. Punzalan


A subset $S$ of $V(G)$ is a dominating set of $G$ if for every $v \in V(G)\backslash S$, there exists $x \in S$ such that $xv \in E(G)$. An identifying code of a graph $G$ is a dominating set $C\subseteq V(G)$ such that for every $v\in V(G)$, $N_G[v]\cap C$ is distinct. In this paper, we investigate the identifying code of some special graphs and give some important results.

Full Text:



O. Ore. emph{Theory of Graphs}. American Mathematical Society, Provedence, R.I., 1962.

E.J. Cockayne, and S.T. Hedetniemi emph{Towards a theory of domination in graphs}, Networks, (1977) 247-261.

M. G. Karpovsky, K. Chakrabarty and L. B. Levitin. On a new class of codes for identifying vertices in graphs. IEEETransactions on Information Theory 44:599–611, 1998.

D. Auger. Minimal identifying codes in trees and planar graphs with large girth, European Journal of Combinatorics

(5):1372–1384, 2010.

I. Charon, O. Hudry and A. Lobstein. Minimizing the size of an identifying or locating-dominating code in a graph is

NP-hard. Theoretical Computer Science 290(3):2109–2120, 2003.

S. Gravier, R. Klasing and J. Moncel. Hardness results and approximation algorithms for identifying codes and locatingdominating codes in graphs. Algorithmic Operations Research 3(1):43–50, 2008.

M. Laifenfeld, A. Trachtenberg and T. Y. Berger-Wolf. Identifying codes and the set cover problem. Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing, Monticello, USA, September 2006.

J. Suomela. Approximability of identifying codes and locating-dominating codes. Information Processing Letters 103(1):28–33, 2007.

E.L. Enriquez, and S.R. Canoy,Jr., emph{Secure Convex Domination in a Graph}. International Journal of Mathematical Analysis, Vol. 9, 2015, no. 7, 317-325.

E.L. Enriquez, emph{Secure Restrained Convex Domination in Graphs}. International Journal of Mathematical Archive, Vol.

, 2017, no. 7, 1-5.

E.M. Kiunisala, and E.L. Enriquez, emph{Clique Secure Domination in Graphs}. Global Journal of Pure and Applied Mathematics. Vol. 12, No. 3 (2016), pp. 2075–2084.

E. L. Enriquez, and S.R. Canoy,Jr., emph{Restrained Convex Dominating Sets in the Corona and the Products of Graphs}. Applied Products of Graphs. Applied Mathematical Sciences, Vol. 9, 2015, no. 78, 3867 - 3873.

C. M. Loquias, E. L. Enriquez, and J. Dayap. emph{Inverse Clique Domination in Graphs}. Recoletos Multidisciplinary

Research Journal. Vol. 4, No. 2 (2017), pp 23-34

C.M. Loquias and E.L. Enriquez, emph{On Secure Convex and Restrained Convex Domination in Graphs}, International

Journal of Applied Engineering Research, Vol. 11, 2016, no. 7, 4707-4710

E.L. Enriquez, emph{Secure restrained domination in the Join and Corona of graphs}. Global Journal of Pure and Applied

Mathematics, 12 (1), 507-516

E.M. Kiunisala, and E.L Enriquez, emph{Inverse Secure Restrained Domination in the Join and Corona of Graphs}. International Journal of Applied Engineering Research. Vol. 11, No. 9 (2016), pp 6676-6679

E.L. Enriquez. S.R. Canoy, Jr., emph{Secure Convex Dominating Sets in Products of Graphs}. Applied

Mathematica Sciences, Vol 9, 2015, no. 56, 2769-2777.

M.P. Baldado, Jr. and E.L. Enriquez, emph{Super Secure Domination in Graphs}, International Journal of Mathematical Archive-8(12), 2017, pp. 145-149


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.


Free Web Counter