Title: Bounds for the L(d, 1): number of diameter 2 graphs, trees and cacti

Authors: Anja Kohl

Addresses: Institute of Discrete Mathematics und Algebra, TU Bergakademie Freiberg, Freiberg 09596, Germany

Abstract: Given a graph G = (V, E) and a positive integer d, an L(d, 1)-labelling of G is a function f : V (G) → {0, 1, …} such that if two vertices x and y are adjacent, then | f (x) − f (y) | ≥ d; if they are at distance 2, then | f (x) − f (y) | ≤ 1. The L(d, 1)-number of G, denoted by λ_d, 1(G), is the smallest number m such that G has an L(d, 1)-labelling with max{f (x) : x ∈ V (G)} = m. It is known that for diameter 2 graphs it holds λ_2,1 ≤ Δ². We will prove Δ²+(d−2)Δ−1 as an upper bound for λ_d,1 for all diameter 2 graphs of order ≤ Δ² − 1 and d ≥ 2. For diameter 2 graphs of maximum degree Δ = 2, 3, 7 and order Δ² + 1 exact values or tight bounds for λ_d,1 will be presented. After this we provide a lower bound for λ_d,1 for trees. At last an upper bound for λ_d,1 for cacti will be established. In particular, we determine λ_1,1 for all cacti and we will show λ_d,1 ≤ Δ + 2d − 2 for cacti having large girth or a large maximum degree Δ.

Keywords: distance 2 labelling; L(2, 1)-labelling; trees; cacti; diameter 2 graphs; mobile networks; frequency assignment; distance constrained labelling; mobile communications.

DOI: 10.1504/IJMNDI.2006.010818

International Journal of Mobile Network Design and Innovation, 2006 Vol.1 No.2, pp.124 - 135

Published online: 05 Sep 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article