On bridged graphs and cop-win graphs (Q1108291): Difference between revisions

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.