کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418866 681723 2014 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On a base exchange game on bispanning graphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On a base exchange game on bispanning graphs
چکیده انگلیسی

We consider the following maker–breaker game on a bispanning graph   i.e. a graph that has a partition of the edge set EE into two spanning trees E1E1 and E2E2. Initially the edges of E1E1 are purple and the edges of E2E2 blue. Maker and breaker move alternately. In a move of the maker a blue edge is colored purple. The breaker then has to recolor a different edge blue in such a way that the purple and the blue edges are spanning trees again. The goal of the maker is to exchange all colors, i.e. to make E1E1 blue and E2E2 purple. We prove that a sufficient but not necessary condition for the breaker to win is that the graph contains a K4K4. Furthermore we characterize the structure of a partition of a wheel into two spanning trees and show that the maker wins on wheels WnWn with n≥4n≥4 and provide an example of a graph where, for some partitions, the maker wins, for some others, the breaker wins. We also describe an efficient algorithm for the recognition of bispanning graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 165, 11 March 2014, Pages 25–36
نویسندگان
, , ,