paired-domination game played in graphs

In this paper, we continue the study of the domination game in graphs introduced by bre{v{s}}ar, klav{v{z}}ar, and rall [siam j. discrete math. 24 (2010) 979--991]. we study the paired-domination version of the domination game which adds a matching dimension to the game. this game is played on a graph g by two players, named dominator and pairer. they alternately take turns choosing vertices of g such that each vertex chosen by dominator dominates at least one vertex not dominated by the vertices previously chosen, while each vertex chosen by pairer is a vertex not previously chosen that is a neighbor of the vertex played by dominator on his previous move. this process eventually produces a paired-dominating set of vertices of g; that is, a dominating set in g that induces a subgraph that contains a perfect matching. dominator wishes to minimize the number of vertices chosen, while pairer wishes to maximize it. the game paired-domination number γpr(g) of g is the number of vertices chosen when dominator starts the game and both players play optimally. let g be a graph on n vertices with minimum degree at least 2. we show that γpr(g)≤45n, and this bound is tight. further we show that if g is (c4,c5)-free, then γpr(g)≤34n, where a graph is (c4,c5)-free if it has no induced 4-cycle or 5-cycle. if g is 2-connected and bipartite or if g is 2-connected and the sum of every two adjacent vertices in g is at least 5, then we show that γpr(g)≤34n.