๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Bridged Graphs Are Cop-Win Graphs: An Algorithmic Proof

โœ Scribed by Victor Chepoi

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
150 KB
Volume
69
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

โœฆ Synopsis

A graph is bridged if it contains no isometric cycles of length greater than three. Anstee and Farber established that bridged graphs are cop-win graphs. According to Nowakowski and Winkler and Quilliot, a graph is a cop-win graph if and only if its vertices admit a linear ordering v 1 , v 2 , ..., v n such that every vertex v i , i>1, is dominated by some neighbour v j , j<i, i.e., every vertex v k , k<i, adjacent to v i is adjacent to v j , too. We present an alternative proof of the result of Anstee and Farber, which allows us to find such an ordering in time linear in the number of edges. Namely, we show that every ordering of the vertices of a bridged graph produced by the breadth-first search is a ``cop-win ordering. '' 1997 Academic Press

๐Ÿ“œ SIMILAR VOLUMES

A characterisation of some 2-connected g
A characterisation of some 2-connected graphs and a comment on an algorithmic proof of Brooks' theorem
โœ Victor Bryant ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 196 KB

A simple characterisation of cycles and complete graphs highlights their significance in Brooks' theorem. It then shows that an algorithmic proof of that theorem. usually dealt with in two cases. is in fact covered by one of the cases. ## 1. Some 2-connected graphs Throughout this paper G = (V, E)