کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647190 1632413 2014 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Solitaire clobber on circulant graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Solitaire clobber on circulant graphs
چکیده انگلیسی

Solitaire Clobber   is a one-player combinatorial game on graphs. Each vertex of a graph GG starts with a black or a white stone. A stone on one vertex can clobber an adjacent stone of the opposite color, removing it and taking its place. The goal is to minimize the number of stones remaining when no further move is possible. An initial configuration is kk-reducible   if it can be reduced to kk stones. A graph is strongly 1-reducible   if, for any vertex vv, any initial configuration that is not monochromatic outside vv can be reduced to one stone, on vv, of either color. Every such graph has a Hamiltonian path ending at vv. For the path PnPn, we prove that the rrth distance power Pnr is strongly 1-reducible when r≥3r≥3 but not when r=2r=2 (Pn2 is 2-reducible). As a consequence, circulant graphs containing edges of lengths 1, 2, and 3 are strongly 1-reducible; we show also that those containing Cn2 are 1-reducible.

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