On bridged graphs and cop-win graphs
type: Item
instance of: scholarly article
title: On bridged graphs and cop-win graphs
zbMATH Open document ID: 0654.05049
DOI: 10.1016/0095-8956(88)90093-7
author: Martin Farber
author: R. P. Anstee
published in: Journal of Combinatorial Theory. Series B
publication date: 1988-01-01T00:00:00Z
review text: A graph is bridged if each its cycle of length \(n\geq 4\) contains a shortcut. It is possible to play on graphs a game of a cop and robber. The cop begins by selecting and occupying a vertex and then the robber does likewise. They then move alternately. Either one can remain in his place or move to any adjacent vertex. The cop wins when both players occupy the same vertex. A graph is cop-win [a definition of R. Nowakowski and P. Winkler, 1980; see also the paper of \textit{R. Nowakowski} and \textit{P. Winkler} in Discrete Math. 43, 235-239 (1983; Zbl 0508.05058] if the cop has a winning strategy. The main result gives the theorem: Every nontrivial component of a bridged graph contains a pair of vertices such that the neighborhood of the first vertex is a subset the neighborhood of the second one. The relationship between bridged graphs and cop-win graphs gives e.g. the statement: A connected graph \({\mathcal G}\) is bridged iff every isometric subgraph of \({\mathcal G}\) (including \({\mathcal G}\) itself) is cop-win.
reviewed by: M.Koman
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4066940
zbMATH Keywords: universal vertex
zbMATH Keywords: chordal graphs
zbMATH Keywords: modular graphs
zbMATH Keywords: simplicial vertex
zbMATH Keywords: geodesically convex set in graph
zbMATH Keywords: bridged graphs
zbMATH Keywords: cop-win graphs
zbMATH Keywords: isometric subgraph
MaRDI profile type: Publication
full work available at URL: 0095-8956(88)90093-7
OpenAlex ID: W2987990768
cites work: Bridged graphs and geodesic convexity
cites work: Convexity in Graphs and Hypergraphs
cites work: On local convexity in graphs
cites work: On the null-homotopy of bridged graphs
cites work: Vertex-to-vertex pursuit in a graph
cites work: Conditions for invariance of set diameters under d-convexification in a graph
description: scientific article; zbMATH DE number 4066940