On subset labelings of trees

Abstract

AbstractFor a nontrivial graph G, a subset labeling of G is a labeling of the vertices of G with nonempty subsets of the set [Formula: see text] for a positive integer r such that two vertices of G have disjoint labels if and only if the vertices are adjacent. The subset index [Formula: see text] of G is the minimum positive integer r for which G has such a subset labeling from the set [Formula: see text]. If T is a tree of diameter d, then [Formula: see text]. It is shown that there are several classes of trees T of diameter d such that [Formula: see text] and for every pair a, b of integers with [Formula: see text], there is a tree T of diameter d such that [Formula: see text] and [Formula: see text]. Sharp bounds are established for the subset indices of the starlike trees [Formula: see text] obtained by subdividing each edge of the star [Formula: see text]a total of r times. Other results and open questions are also presented on subset indices of trees.

Keywords

• Subset labeling
• subset index
• tree
• 05C05
• 05C75
• 05C78