کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648383 | 1632438 | 2010 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Cop-win graphs with maximum capture-time
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We present an upper bound n−4n−4 for the maximum length of a cop and robber game (the capture-time ) on a cop-win graph of order nn. This bound matches the known lower bound. We analyze the structure of the class of all graphs attaining this maximum and describe an inductive construction of the entire class.A cop and robber game is a two-player vertex-to-vertex pursuit combinatorial game where the players stand on the vertices of a graph and alternate in moving to adjacent vertices. Cop’s goal is to capture the robber by occupying the same vertex as the robber, robber’s goal is to avoid capture.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issues 10–11, 6 June 2010, Pages 1557–1563
Journal: Discrete Mathematics - Volume 310, Issues 10–11, 6 June 2010, Pages 1557–1563
نویسندگان
Tomáš Gavenčiak,