The watchman's walk problem on directed graphs

zbMATH Open1468.05094arXiv2007.13901MaRDI QIDQ5000299FDOQ5000299

Danny Dyer, Jared Howell, Brittany Pittman

Publication date: 12 July 2021

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.

Full work available at URL: https://arxiv.org/abs/2007.13901

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

zbMATH Keywords

watchman's walk problemminimum closed dominating walk

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On a Problem in Graph Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast parallel algorithms for finding hamiltonian paths and cycles in a tournament
• A characterization of unique tournaments
• Bounds on watching and watching graph products
• Even time constraints on the watchman's walk
• A time-constrained variation of the watchman's walk problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The watchman's walk problem on directed graphs
• Title not available (Why is that?)

Cited In (4)

• The watchman's walk problem on directed graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Even time constraints on the watchman's walk

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)