کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648105 1342393 2012 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Parity in graph sharing games
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Parity in graph sharing games
چکیده انگلیسی

Two players share a connected graph with non-negative weights on the vertices. They alternately take the vertices one by one and collect their weights. The rule they have to obey is that the taken part of the graph must be connected after each move. We present a strategy for the first player to get at least 1/41/4 of a tree with an odd number of vertices. The parity condition is necessary: it is easy to find even trees with the first player’s guaranteed outcome tending to zero. In general there are odd graphs with arbitrarily small outcome of the first player, but all known constructions are intricate. We suspect a kind of general parity phenomenon, namely, that the first player can secure a substantial fraction of the weight of any KnKn-minor-free graph with an odd number of vertices. We discuss analogies with another variant of this game, called the graph-grabbing game, where the players have to keep the remaining (not taken) part connected all the time.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 10, 28 May 2012, Pages 1788–1795
نویسندگان
, ,