Premium
Convex labelings of trees
Author(s) -
Dow Stephen J.,
Rall Douglas F.,
Slater Peter J.
Publication year - 1987
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190110110
Subject(s) - combinatorics , mathematics , vertex (graph theory) , tree (set theory) , regular polygon , convex set , order (exchange) , convex combination , discrete mathematics , graph , convex optimization , geometry , finance , economics
A convex labeling of a tree T of order n is a one‐to‐one function f from the vertex set of T into the nonnegative integers, so that f(y) ⩽ (f(x) + f(z)) /2 for every path x, y, z of length 2 in T . If, in addition, f(v) ⩽ n − 1 for every vertex v of T , then f is a perfect convex labeling and T is called a perfectly convex tree. Jamison introduced this concept and conjectured that every tree is perfectly convex. We show that there exists an infinite class of trees, none of which is perfectly convex, and in fact prove that for every n there exists a tree of order n which requires a convex labeling with maximum value at least 6 n /5 – 22. We also prove that every tree of order n admits a convex labeling with maximum label no more than n 2 /8 + 2. In addition, we present some constructive methods for obtaining perfect convex labelings of large classes of trees.