Roozbayani, M., Maimani, H., Tehranian, A. (2014). Watching systems of triangular graphs. Transactions on Combinatorics, 3(1), 51-57. doi: 10.22108/toc.2014.4127

Maryam Roozbayani; Hamidreza Maimani; Abolfazl Tehranian. "Watching systems of triangular graphs". Transactions on Combinatorics, 3, 1, 2014, 51-57. doi: 10.22108/toc.2014.4127

Roozbayani, M., Maimani, H., Tehranian, A. (2014). 'Watching systems of triangular graphs', Transactions on Combinatorics, 3(1), pp. 51-57. doi: 10.22108/toc.2014.4127

Roozbayani, M., Maimani, H., Tehranian, A. Watching systems of triangular graphs. Transactions on Combinatorics, 2014; 3(1): 51-57. doi: 10.22108/toc.2014.4127

^{1}Science and Research Branch, Islamic Azad University

^{2}Shahid Rajaee Teacher Training University

Abstract

A watching system in a graph $G=(V, E)$ is a set $W=\{\omega_{1}, \omega_{2}, \dots, \omega_{k}\}$, where $\omega_{i}=(v_{i}, Z_{i}), v_{i}\in V$ and $Z_{i}$ is a subset of closed neighborhood of $v_{i}$ such that the sets $L_{W}(v)=\{\omega_{i}: v\in Z_{i}\}$ are non-empty and distinct, for any $v\in V$. In this paper, we study the watching systems of line graph $K_{n}$ which is called triangular graph and denoted by $T(n)$. The minimum size of a watching system of $G$ is denoted by $\omega(G)$. We show that $\omega(T(n))=\lceil\frac{2n}{3}\rceil$.

D. Auger (2010). Minimal identifying codes in trees and
planar graphs with large girth. European J. Combin.. 31 (5), 1372-1384

2

D. Auger, I. Charon, O. Hurdy and A. Lobstein (2013). Watching systems in graphs: an extension of identifying codes. Discrete Appl. Math.. 161 (12), 1674-1685

3

I. Charon, O. Hudry and A. Lobstein (2003). Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard. Theoret. Comput. Sci.. 290 (3), 2109-2120

4

I. Charon, O. Hudry and A. Lobstein (2007). Extremal cardinalities for identifying and locating-dominating codes in graphs. Discrete
Math.. 307 (3-5), 356-366

5

R. Diestel (1997). Graph theory. Translated from the 1996 German original, Graduate Texts in Mathematics, Springer-Verlag, New York. 173

6

M. G. Karpovsky, K. Chakrabarty and L. B. Levitin (1998). On a new class of codes for identifying vertices in graphs. IEEE
Trans. Inform. Theory. 44, 599-611

7

F. Foucaud, E. Guerrini, M. Kovse, R. Naserasr, A. Parreau and P. Valicov (2011). Extremal graphs for the identifying code
problem. European J. Combin.. 32 (4), 628-638

8

F. Foucauda, S. Gravierb, R. Naserasra, A. Parreaub and P. Valicova (2013). Identifying codes in line graphs. J. Graph Theory. 37 (4), 425-448

9

F. Foucaud, R. Klasing, A. Kosowski and A. Raspaud (2012). On the size of identifying codes in triangle-free graphs. Discrete Appl. Math.. 160 (10-11), 1532-1546