# The game L (d, 1) -labeling problem of graphs

Ma Lian Chia, Huei Ni Hsu, David Kuo, Sheng Chyang Liaw, Zi Teng Xu

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

## Abstract

Let G be a graph and let k be a positive integer. Consider the following two-person game which is played on G: Alice and Bob alternate turns. A move consists of selecting an unlabeled vertex v of G and assigning it a number a from 0,1,2,...,k satisfying the condition that, for all u∈V(G),u is labeled by the number b previously, if d(u,v)=1, then |a-b|<d, and if d(u,v)=2, then |a-b|<1. Alice wins if all the vertices of G are successfully labeled. Bob wins if an impasse is reached before all vertices in the graph are labeled. The game L(d,1)-labeling number of a graph G is the least k for which Alice has a winning strategy. We use λ1d(G) to denote the game L(d,1)-labeling number of G in the game Alice plays first, and use λ2d(G) to denote the game L(d,1)-labeling number of G in the game Bob plays first. In this paper, we study the game L(d,1)-labeling numbers of graphs. We give formulas for λ1d( Kn) and λ2d( Kn), and give formulas for λ1d(Km, n) for those d with d<maxm,n.

Original language English 3037-3045 9 Discrete Mathematics 312 20 https://doi.org/10.1016/j.disc.2012.07.002 Published - 28 Oct 2012

## Keywords

• Complete bipartite graphs
• Complete graphs
• Game L (d, 1) -labeling

## Fingerprint

Dive into the research topics of 'The game L (d, 1) -labeling problem of graphs'. Together they form a unique fingerprint.