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

Let GG be a graph and let kk be a positive integer. Consider the following two-person game which is played on GG: Alice and Bob alternate turns. A move consists of selecting an unlabeled vertex vv of GG and assigning it a number aa from {0,1,2,…,k}{0,1,2,…,k} satisfying the condition that, for all u∈V(G),uu∈V(G),u is labeled by the number bb previously, if d(u,v)=1d(u,v)=1, then |a−b|≥d|a−b|≥d, and if d(u,v)=2d(u,v)=2, then |a−b|≥1|a−b|≥1. Alice wins if all the vertices of GG are successfully labeled. Bob wins if an impasse is reached before all vertices in the graph are labeled. The game  L(d,1)L(d,1)-labeling number   of a graph GG is the least kk for which Alice has a winning strategy. We use λ̃1d(G) to denote the game L(d,1)L(d,1)-labeling number of GG in the game Alice plays first, and use λ̃2d(G) to denote the game L(d,1)L(d,1)-labeling number of GG in the game Bob plays first. In this paper, we study the game L(d,1)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 dd with d≥max{m,n}d≥max{m,n}.