DOMINATION NUMBER AND WATCHING NUMBER OF SUBDIVISION CONSTRUCTION OF GRAPHS
Abstract
In light of the results of a domination number of the subdivision of a graph G, we determine an upper bound of the watching number of S(G). In addition, we obtain a condition with which the upper bound becomes sharp.
Keywords
Full Text:
PDFReferences
D. Auger, I. Charon, O. Hudry and A. Lobstein: Watching systems in graphs: an extension of identifying codes. Discrete Applied Mathematics. 161(12) (2013) 1674-1685.
D. Auger, I. Charon, O. Hudry and A. Lobstein: Maximum size of a minimum watching system and the graphs achieving the bound. Discrete Applied Mathematics. 164 (2014) 20-33.
F. Foucaud, S. Gravier, R. Naserasr, A. Parreau and P. Valicov: Identifying codes in line graphs. Journal of Graph Theory. 73(4) (2013) 425-448.
F. Foucaud and G. Perarnau: Bounds for identifying codes in terms of degree parameters. The electronic journal of combinatorics. 19 (1) (2012) 32.
M. Ghorbani, M. Dehmer, H.R. Maimani, S. Maddah, M. Roozbayani and F. Emmert-Streib: The watching system as a generalization of identifying code. Appl. Math. Comput. (2020).
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.
Hernando Mart´ın MD, Mora Gin´e M and Pelayo Melero IM: Watching systems in complete bipartite graphs. In: VIII Jornadas de Matem´atica Discreta y Algor´ıtmica, Almer´ıa. 11(13) (2012) 53-60.
O. Hudry and A. Lobstein: Unique (optimal) solutions: Complexity results for identifying and locating dominating codes. Theoretical Computer Science. 767 (2019) 83-102.
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.
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.
Mohammad A. Iranmanesh and N. Moghaddami: Domination parameters and diameter of abelian cayley graph. Facta Universitatis, Series: Mathematics and Informatics. 4 (2021) 695-715.
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.
M. Roozbayani, H. Maimani and A. Tehranian Watching systems of triangular graphs. Transactions on Combinatorics. 3(1) (2014) 51-57.
M. Roozbayani and H. R. Maimani: Identifying codes and watching systems in kneser graphs. Discrete Mathematics, Algorithms and Applications. 9(01) (2017) 1750007.
D.F. Rall and K. Wash: Identifying codes of the direct product of two cliques. European Journal of Combinatorics. 36 (2014) 159-171.
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.
A. Shaminejad, E. Vatandoost and K. Mirasheh: The identifying code number and Mycielski’s construction of graphs. Transactions on Combinatrics. 11 (4) (2022) 309-316 .
DOI: https://doi.org/10.22190/FUMI221126003M
Refbacks
- There are currently no refbacks.
ISSN 0352-9665 (Print)