The L (2, 1)-labeling on Cartesian sum of graphs

Zhendong Shao, Dapeng Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)

Abstract

An L (2, 1)-labeling 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)-labeling number λ (G) of G is the smallest number k such that G has an L (2, 1)-labeling with max {f (v) : v ∈ V (G)} = k. Griggs and Yeh conjecture that λ (G) ≤ Δ2 for any simple graph with maximum degree Δ ≥ 2. This paper considers the graph formed by the Cartesian sum of two graphs. As corollaries, the new graph satisfies the above conjecture (with minor exceptions).
Original languageEnglish
Pages (from-to)843-848
Number of pages6
JournalApplied Mathematics Letters
Volume21
Issue number8
DOIs
Publication statusPublished - 1 Aug 2008

Keywords

  • Channel assignment
  • Graph Cartesian sum
  • L (2, 1)-labeling

ASJC Scopus subject areas

  • Applied Mathematics

Cite this