Proof of a conjecture for the watching number

Document Type : Full Length Article

Authors

1 ‎Department of Basic Science, ‎Imam Khomeini International University‎‎,‎Qazvin‎, ‎Iran

2 ‎Department of Pure Mathematics, ‎Faculty of Mathematical Sciences‎, ‎University of Guilan‎‎, ‎Rasht‎, ‎Iran

3 Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran

Abstract

In this paper, we prove that for every connected graph G of order n, the watching number of its subdivision graph S(G) is exactly n. This result confirms a conjecture previously proposed by Vatandoost et al. [7].

Graphical Abstract

Proof of a conjecture for the watching number

Keywords

Main Subjects

References

 [1] D. Auger, I. Charon, O. Hudry, A. Lobstein, Watching systems in graphs: an extension of identifying codes, Discrete Applied Mathematics 161 (2013) 1674–1685. https://doi.org/10.1016/j.dam.2011.04.025
[2] D. Auger, I. Charon, O. Hudry, A. Lobstein, Maximum size of a minimum watching system and the graphs achieving the bound, Discrete Applied Mathematics 164 (2014) 20–33. https://doi.org/10.1016/j.dam.2012.08.028
[3] F. Foucaud, S. Gravier, R. Naserasr, A. Parreau, P. Valicov, Identifying codes in line graphs, Journal of Graph Theory 73 (2013) 425–448. https://doi.org/10.1002/jgt.21686
[4] F. Foucaud, G. Perarnau, Bounds for identifying codes in terms of degree parameters, Electronic Journal of Combinatorics 19 (2012) P32. https://doi.org/10.37236/2036
[5] M. D. Hernando, M. Mora, I. M. Pelayo, Watching systems in complete bipartite graphs, VIII Jornadas de Matemática Discreta y Algortímica, Almería (2012) 53–60.
[6] O. Hudry, A. Lobstein, Unique (optimal) solutions: Complexity results for identifying and locating dominating codes, Theoretical Computer Science 767 (2019) 83–102. https://doi.org/10.1016/j.tcs.2018.09.034
[7] K. Mirasheh, A. Abbasi, E. Vatandoost, Domination number and watching number of subdivision construction of graphs, Facta Universitatis, Series: Mathematics and Informatics 40 (2025) 33–43. https://doi.org/10.22190/FUMI221126003M
[8] M. Roozbayani, H. Maimani, A. Tehranian, Watching systems of triangular graphs, Transactions on Combinatorics 3 (2014) 51–57. https://doi.org/10.22108/toc.2014.4127 
 [9] M. Roozbayani, H. R. Maimani, Identifying codes and watching systems in Kneser graphs, Discrete Mathematics, Algorithms and Applications 9 (2017) 1750007. https://doi.org/10.1142/S1793830917500070
[10] D. F. Rall, K. Wash, Identifying codes of the direct product of two cliques, European Journal of Combinatorics 36 (2014) 159–171. https://doi.org/10.1016/j.ejc.2013.07.002
[11] A. Shaminejad, E. Vatandoost, K. Mirasheh, The identifying code number and Mycielski’s construction of graphs, Transactions on Combinatorics 11 (2022) 309–316. https://doi.org/10.22108/toc.2021.126368.1794 
Journal of Discrete Mathematics and Its Applications
Volume 11, Issue 3
September 2026
Pages 193-198

Files

History

  • Receive Date: 22 October 2025
  • Revise Date: 09 February 2026
  • Accept Date: 09 March 2026
  • First Publish Date: 30 August 2026
  • Publish Date: 01 September 2026

Share

How to cite

Statistics