1. The game -labeling problem of graphs
- Author
-
Chia, Ma-Lian, Hsu, Huei-Ni, Kuo, David, Liaw, Sheng-Chyang, and Xu, Zi-teng
- Subjects
- *
GAME theory , *GRAPH theory , *PATHS & cycles in graph theory , *INTEGERS , *MATHEMATICAL formulas , *MATHEMATICAL analysis - Abstract
Abstract: Let be a graph and let be a positive integer. Consider the following two-person game which is played on : Alice and Bob alternate turns. A move consists of selecting an unlabeled vertex of and assigning it a number from satisfying the condition that, for all is labeled by the number previously, if , then , and if , then . Alice wins if all the vertices of are successfully labeled. Bob wins if an impasse is reached before all vertices in the graph are labeled. The game -labeling number of a graph is the least for which Alice has a winning strategy. We use to denote the game -labeling number of in the game Alice plays first, and use to denote the game -labeling number of in the game Bob plays first. In this paper, we study the game -labeling numbers of graphs. We give formulas for and , and give formulas for for those with . [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF