Game domination number

N. Alon, József Balogh, Béla Bollobás, Tamás Szabó

Research output: Contribution to journalArticle

12 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)23-33
Number of pages11
JournalDiscrete Mathematics
Volume256
Issue number1-2
DOIs
StatePublished - Sep 28 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • Directed graph
  • Domination number
  • Orientation game

Fingerprint Dive into the research topics of 'Game domination number'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Balogh, J., Bollobás, B., & Szabó, T. (2002). Game domination number. Discrete Mathematics, 256(1-2), 23-33. https://doi.org/10.1016/S0012-365X(00)00358-7