کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647187 1632413 2014 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Edge-critical cops and robber in planar graphs
ترجمه فارسی عنوان
پلیس انتقادی انتقاد و دزدی در نمودارهای مسطح
کلمات کلیدی
پیگیری بازی، پلیس و دزد لبه انتقادی، نمودار پلانار
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

The problem is to determine the number of ‘cops’ needed to capture a ‘robber’ in a game in which the cops always know the location of the robber, and the cops and robber move alternately along edges of a reflexive graph. The cops capture the robber if one of them occupies the same vertex as the robber at any time in the game. A cop-win graph is one in which a single cop has a winning strategy. A graph is cop-win edge-critical with respect to edge addition (respectively, deletion) when the original graph is not cop-win, but the addition (deletion) of any edge results in a cop-win graph. In this paper, edge-critical planar graphs are characterized.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 329, 28 August 2014, Pages 1–11
نویسندگان
,