Identifying Code of Some Special Graphs

Article Sidebar

PDF
Published: Sep 21, 2018

Main Article Content

Enrico Limbo Enriquez
University of San Carlos
Jesus L. Ranara
Abellana National School
Carmelita N. Loquias
University of San Carlos
Grace M. Estrada
University of San Carlos
Teodora J. Punzalan
University of San Carlos

Abstract

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.

Downloads

Download data is not yet available.

Article Details

How to Cite
Enriquez, E. L., Ranara, J. L., Loquias, C. N., Estrada, G. M., & Punzalan, T. J. (2018). Identifying Code of Some Special Graphs. Journal of Global Research in Mathematical Archives(JGRMA), 5(9), 01–08. Retrieved from https://www.jgrma.com/index.php/jgrma/article/view/503
Issue
Vol. 5 No. 9 (2018): September-2018
Section
Research Paper

Open Access: This is an open-access journal. All articles published in the Journal of Global Research in Mathematical Archives(JGRMA) are made immediately and permanently available under the Creative Commons Attribution 4.0 International (CC BY 4.0) License. Authors retain the copyright of their work and grant Journal of Global Research in Mathematical Archives(JGRMA)  the right of first publication. This license permits unrestricted use, distribution, adaptation, and reproduction in any medium or format, including commercial use, provided the original author(s), source, and license are properly acknowledged.

Google Scholar Indexed | DOI Enabled | OAI-PMH Compliant | Open Access Journal

Author Biographies

Enrico Limbo Enriquez, University of San Carlos

Associate Professor

Mathematics Department

University of San Carlos

Philippines

Jesus L. Ranara, Abellana National School

Instructor

Department o Mathematics

Abellan National School

Cebu City, Philippines

Carmelita N. Loquias, University of San Carlos

Assistant Professor

Mathematics Department

University of San Carlos

Philippines

Grace M. Estrada, University of San Carlos

Assistant Professor

Mathematics Department

University of San Carlos

Philippines

Teodora J. Punzalan, University of San Carlos

Assistant Professor

Mathematics Department

University of San Carlos

Philippines

References

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. http://dx.doi.org/10.12988/ams.2015.52114

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