The watchman's walk problem on directed graphs

MaRDI QIDQ5000299zbMATH OpenFDO

Authors Danny Dyer, Jared Howell, Brittany Pittman

Publication date 12 July 2021

Full work available at URL https://arxiv.org/abs/2007.13901, http://ajc.maths.uq.edu.au/pdf/80/ajc_v80_p197.pdf

zbMATH Keywords

watchman's walk problemminimum closed dominating walk

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random walks on graphs (05C81)

Abstract: In a graph, a watchman's walk is a minimum closed dominating walk. Given a graph $G$ and a single watchman, the length of a watchman's walk in $G$ (the watchman number) is denoted by $w(G)$ and the typical goals of the watchman's walk problem is to determine $w(G)$ and find a watchman's walk in $G$. In this paper, we extend the watchman's walk problem to directed graphs. In a directed graph, we say that the watchman can only move to and see the vertices that are adjacent to him relative to outgoing arcs. That is, a watchman's walk is oriented and domination occurs in the direction of the arcs. The directed graphs this paper focuses on are families of tournaments and orientations of complete multipartite graphs. We give bounds on the watchman number and discuss its relationship to variants of the domination number.

Recommendations

• Bounds on watching and watching graph products
• scientific article; zbMATH DE number 6700524
• A time-constrained variation of the watchman's walk problem
• Even time constraints on the watchman's walk
• scientific article; zbMATH DE number 1472156

Cites work

• scientific article; zbMATH DE number 6700524 (Why is no real title available?)
• scientific article; zbMATH DE number 3150485 (Why is no real title available?)
• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1472156 (Why is no real title available?)
• scientific article; zbMATH DE number 3013308 (Why is no real title available?)
• scientific article; zbMATH DE number 1890833 (Why is no real title available?)
• scientific article; zbMATH DE number 2104726 (Why is no real title available?)
• scientific article; zbMATH DE number 2114506 (Why is no real title available?)
• scientific article; zbMATH DE number 1416469 (Why is no real title available?)
• scientific article; zbMATH DE number 3226832 (Why is no real title available?)
• scientific article; zbMATH DE number 3303831 (Why is no real title available?)
• A characterization of unique tournaments
• A time-constrained variation of the watchman's walk problem
• Bounds on watching and watching graph products
• Even time constraints on the watchman's walk
• Fast parallel algorithms for finding hamiltonian paths and cycles in a tournament
• On a Problem in Graph Theory
• The watchman's walk problem on directed graphs
• Watchman's walk of Steiner triple system block intersection graphs

Cited in

(8)

• The watchman's walk problem on directed graphs
• Even time constraints on the watchman's walk
• Bounds on watching and watching graph products
• scientific article; zbMATH DE number 1472156 (Why is no real title available?)
• scientific article; zbMATH DE number 1890833 (Why is no real title available?)
• A time-constrained variation of the watchman's walk problem
• On the watching number of graphs
• Watchman's walk of Steiner triple system block intersection graphs

This page was built for publication: The watchman's walk problem on directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5000299)