UP - logo
E-resources
Peer reviewed Open access
  • L ( j , k ) -labelling and ...
    Juan, Justie Su-Tzu; Liu, Daphne Der-Fen; Chen, Li-Yueh

    Discrete Applied Mathematics, 03/2010, Volume: 158, Issue: 6
    Journal Article

    Let G be a graph. For two vertices u and v in G , we denote d ( u , v ) the distance between u and v . Let j , k be positive integers with j ⩾ k . An L ( j , k ) - labelling for G is a function f : V ( G ) → { 0 , 1 , 2 , … } such that for any two vertices u and v , | f ( u ) − f ( v ) | is at least j if d ( u , v ) = 1 ; and is at least k if d ( u , v ) = 2 . The span of f is the difference between the largest and the smallest numbers in f ( V ) . The λ j , k - number for G , denoted by λ j , k ( G ) , is the minimum span over all L ( j , k ) -labellings of G . We introduce a new parameter for a tree T , namely, the maximum ordering-degree, denoted by M ( T ) . Combining this new parameter and the special family of infinite trees introduced by Chang and Lu (2003)  3, we present upper and lower bounds for λ j , k ( T ) in terms of j , k , M ( T ) , and Δ ( T ) (the maximum degree of T ). For a special case when j ⩾ Δ ( T ) k , the upper and the lower bounds are k apart. Moreover, we completely determine λ j , k ( T ) for trees T with j ⩾ M ( T ) k .