Search

Given a graph G and a function h from E ( G ) to N , the h -subdivision of G , denoted by G ( h ) , is the graph obtained from G by replacing each edge u v in G with a path P : u x u v 1 x u v 2 … x u v n − 1 v , where n = h ( u v ) . When h ( e ) = c is a constant for all e ∈ E ( G ) , we use G ( c ) to replace G ( h ) . Given a graph G , an L ( 2 , 1 ) -labeling of G is a function f from the vertex set V ( G ) to the set of all nonnegative integers such that | f ( x ) − f ( y ) | ≥ 2 if d G ( x , y ) = 1 , and | f ( x ) − f ( y ) | ≥ 1 if d G ( x , y ) = 2 . A k - L ( 2 , 1 ) -labeling is an L ( 2 , 1 ) -labeling such that no label is greater than k . The L ( 2 , 1 ) -labeling number of G , denoted by λ ( G ) , is the smallest number k such that G has a k - L ( 2 , 1 ) -labeling. We study the L ( 2 , 1 ) -labeling numbers of subdivisions of graphs in this paper. We prove that λ ( G ( 3 ) ) = Δ ( G ) + 1 for any graph G with Δ ( G ) ≥ 4 , and show that λ ( G ( h ) ) = Δ ( G ) + 1 if Δ ( G ) ≥ 5 and h is a function from E ( G ) to N so that h ( e ) ≥ 3 for all e ∈ E ( G ) , or if Δ ( G ) ≥ 4 and h is a function from E ( G ) to N so that h ( e ) ≥ 4 for all e ∈ E ( G ) . [ABSTRACT FROM AUTHOR]

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]