Distance labellings of graphs

Zhendong Shao, Dapeng Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)


An L(2, 1)-labelling of a graph 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(x,y) = 1 and |f(x) - f(y)| ≥ 1 if d(x,y) = 2, where d(x,y) denotes the distance between x and y in G. The L(2,1)-labelling number λ(G) of G is the smallest number k such that G has an L(2, 1)-labelling with max{f(v) : v € V(G)} = k. Griggs and Yeh conjecture that λ(G) ≤ Δ2for any simple graph with maximum degree A Δ≥ 2. This article considers the graphs formed by the cartesian product of n(n ≥ 2) graphs. The new graph satisfies the above conjecture (with minor exceptions). Moreover, we generalize our results in [19].
Original languageEnglish
Pages (from-to)23-31
Number of pages9
JournalArs Combinatoria
Publication statusPublished - 1 Jan 2013

ASJC Scopus subject areas

  • Mathematics(all)

Cite this