Roman game domination number of a graph

The Roman game domination number of an undirected graph G is defined by the following game. Players A and D orient the edges of the graph G alternately, with D playing first, until all edges are oriented. Player D (frequently called Dominator) tries to minimize the Roman domination number of the res...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial optimization 2017-02, Vol.33 (2), p.713-725
Main Authors: Bahremandpour, A., Sheikholeslami, S. M., Volkmann, L.
Format: Article
Language:English
Subjects:
Combinatorics
Convex and Discrete Geometry
Game theory
Graph theory
Mathematical Modeling and Industrial Mathematics
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Players
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Roman game domination number of an undirected graph G is defined by the following game. Players A and D orient the edges of the graph G alternately, with D playing first, until all edges are oriented. Player D (frequently called Dominator) tries to minimize the Roman domination number of the resulting digraph, while player A (Avoider) tries to maximize it. This game gives a unique number depending only on G , if we suppose that both A and D play according to their optimal strategies. This number is called the Roman game domination number of G and is denoted by γ R g ( G ) . In this paper we initiate the study of the Roman game domination number of a graph and we establish some bounds on γ R g ( G ) . We also determine the Roman game domination number for some classes of graphs.
ISSN:1382-6905
1573-2886
DOI:10.1007/s10878-016-0001-4