Game domination subdivision number of a graph

Game domination subdivision number of a graph

0.00 Avg rating0 Votes
Article ID: iaor201526110
Volume: 30
Issue: 1
Start Page Number: 109
End Page Number: 119
Publication Date: Jul 2015
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: combinatorial optimization, graphs
Abstract:

The game domination subdivision number of a graph G equ1 is defined by the following game. Two players D equ2 and A equ3 , D equ4 playing first, alternately mark or subdivide an edge of G equ5 which is not yet marked nor subdivided. The game ends when all the edges of G equ6 are marked or subdivided and results in a new graph G equ7 . The purpose of D equ8 is to minimize the domination number γ ( G ) equ9 of G equ10 while A equ11 tries to maximize it. If both A equ12 and D equ13 play according to their optimal strategies, γ ( G ) equ14 is well defined. We call this number the game domination subdivision number of G equ15 and denote it by γ gs ( G ) equ16 . In this paper we initiate the study of the game domination subdivision number of a graph and present sharp bounds on the game domination subdivision number of a tree.

Reviews

Required fields are marked *. Your email address will not be published.