Optimal L(3,2,1)-labeling of trees

Abstract

Given a graph G, an [Formula: see text]-labeling of G is an assignment f of non-negative integers (labels) to the vertices of G such that [Formula: see text] if [Formula: see text] (i = 1, 2, 3). For a non-negative integer k, a k-[Formula: see text]-labeling is an [Formula: see text]-labeling such that no label is greater than k. The [Formula: see text]-labeling number of G, denoted by [Formula: see text], is the smallest number k such that G has a k-[Formula: see text]-labeling. Chia proved that the [Formula: see text]-labeling number of a tree T with maximum degree Δ can have one of three values: [Formula: see text] and [Formula: see text]. This paper gives some sufficient conditions for [Formula: see text] and [Formula: see text], respectively. As a result, the [Formula: see text]-labeling numbers of complete m-ary trees, spiders and banana trees are completely determined.

Keywords

• Channel assignment
• -labeling
• trees
• 05C78
• 05C15