DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

D. Dyer

Danny Dyer

St. John's Campus, Memorial University of Newfoundland

email: dyer@mun.ca

0000-0001-6921-1517

J. Howell

Jared Howell

Grenfell Campus, Memorial University of Newfoundland

email: jahowell@grenfell.mun.ca

0000-0003-4386-9876

Title:

Bounds on watching and watching graph products

PDF

Source:

Discussiones Mathematicae Graph Theory 42(1) (2022) 63-79

Received: 2018-09-17 , Revised: 2019-05-07 , Accepted: 2019-07-03 , Available online: 2019-09-21 , https://doi.org/10.7151/dmgt.2239

Abstract:

A watchman's walk for a graph $G$ is a minimum-length closed dominating walk, and the length of such a walk is denoted $(G)$. We introduce several lower bounds for such walks, and apply them to determine the length of watchman's walks in several grids.

Keywords:

watchman's walk, domination, graph products

References:

  1. I. Beaton, R. Begin, S. Finbow and C.M. van Bommel,, Even time constraints on the watchman's walk, Australas. J. Combin. 56 (2013) 113–121.
  2. T.Y. Chang, Domination Numbers of Grid Graphs (PhD. Thesis, ProQuest LLC, Ann Arbor, MI, University of South Florida, 1992).
  3. K. Clarke, The Watchman's Walk on Cartesian Products and Circulants, Thesis (Honours)–-Memorial University of Newfoundland.
  4. S. Crevals and P.R.J. Östergård, Independent domination of grids, Discrete Math. 338 (2015) 1379–1384.
    https://doi.org/10.1016/j.disc.2015.02.015
  5. C. Davies, S. Finbow, B.L. Hartnell, Q. Li and K. Schmeisser, The watchman problem on trees, Bull. Inst. Combin. Appl. 37 (2003) 35–43.
  6. D. Dyer and R. Milley, A time-constrained variation of the watchman's walk problem, Australas. J. Combin. 53 (2012) 97–108.
  7. D. Dyer and J. Howell, The multiplicity of watchman's walks, Congr. Numer. 226 (2016) 301–317.
  8. D. Dyer and J. Howell, Watchman's walks of Steiner triple system block intersection graphs, Australas. J. Combin. 68 (2017) 23–34.
  9. S. Finbow, M.E. Messinger and M.F. van Bommel, Eternal domination on {$3× n$} grid graphs, Australas. J. Combin. 61 (2015) 156–174.
  10. D. Gonçalves, A. Pinlou, M. Rao and S. Thomassé, The domination number of grids, SIAM J. Discrete Math. 25 (2011) 1443–1453.
    https://doi.org/10.1137/11082574
  11. B.L. Hartnell, D.F. Rall and C.A. Whitehead, The watchman's walk problem: An introduction, Congr. Numer. 130 (1998) 149–155.
  12. B.L. Hartnell and C.A. Whitehead, Minimum dominating walks in Cartesian product graphs, Util. Math. 65 (2004) 73–82.
  13. B.L. Hartnell and C.A. Whitehead, Minimum dominating walks on graphs with large circumference, Util. Math. 78 (2009) 33–40.
Close