کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4646606 1342307 2016 8 صفحه PDF سفارش دهید دانلود رایگان
عنوان انگلیسی مقاله ISI
Subdivisions in the Robber Locating game
ترجمه فارسی عنوان
تقسیمات در بازی محل ربایی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

We consider a game in which a cop searches for a moving robber on a graph using distance probes, which is a slight variation on one introduced by Seager. Carraher, Choi, Delcourt, Erickson and West showed that for any nn-vertex graph GG there is a winning strategy for the cop on the graph G1/mG1/m obtained by replacing each edge of GG by a path of length mm, if m⩾nm⩾n. They conjectured that this bound was best possible for complete graphs, but the present authors showed that in fact the cop wins on Kn1/m if and only if m⩾n/2m⩾n/2, for all but a few small values of nn. In this paper we extend this result to general graphs by proving that the cop has a winning strategy on G1/mG1/m provided m⩾n/2m⩾n/2 for all but a few small values of nn; this bound is best possible. We also consider replacing the edges of GG with paths of varying lengths.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 11, 6 November 2016, Pages 2804–2811
نویسندگان
, , ,
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت