TY - JOUR

T1 - Game domination number

AU - Alon, N.

AU - Balogh, József

AU - Bollobás, Béla

AU - Szabó, Tamás

N1 - Funding Information:
∗Corresponding author. E-mail address: tszabo@weber.edu (T. Szabo$). 1Research partly supported by OTKA grants F021271 and F026049.

PY - 2002/9/28

Y1 - 2002/9/28

N2 - The game domination number-of a (simple, undirected) graph is defined by the following game. Two players, A and D, orient the edges of the graph alternately until all edges are oriented. Player D starts the game, and his goal is to decrease the domination number of the resulting digraph, while A is trying to increase it. The game domination number of the graph G, denoted by γg(G), is the domination number of the directed graph resulting from this game. This is well defined if we suppose that both players follow their optimal strategies. We determine the game domination number for several classes of graphs and provide general inequalities relating it to other graph parameters.

AB - The game domination number-of a (simple, undirected) graph is defined by the following game. Two players, A and D, orient the edges of the graph alternately until all edges are oriented. Player D starts the game, and his goal is to decrease the domination number of the resulting digraph, while A is trying to increase it. The game domination number of the graph G, denoted by γg(G), is the domination number of the directed graph resulting from this game. This is well defined if we suppose that both players follow their optimal strategies. We determine the game domination number for several classes of graphs and provide general inequalities relating it to other graph parameters.

KW - Directed graph

KW - Domination number

KW - Orientation game

UR - http://www.scopus.com/inward/record.url?scp=33750997636&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33750997636&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(00)00358-7

DO - 10.1016/S0012-365X(00)00358-7

M3 - Article

AN - SCOPUS:33750997636

VL - 256

SP - 23

EP - 33

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-2

ER -