✦ LIBER ✦

Convex labelings of trees

✍ Scribed by Stephen J. Dow; Douglas F. Rall; Peter J. Slater

Publisher: John Wiley and Sons
Year: 1987
Tongue: English
Weight: 456 KB
Volume: 11
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190110110

No coin nor oath required. For personal study only.

✦ Synopsis

A convex labeling of a tree T o f order n is a one-to-one function f from the vertex set of Tinto the nonnegative integers, so that f ( y ) 5 ( f ( x ) t f(z))/2 for every path x, y, z of length 2 in T. If, in addition, f (v) I 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 6n/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, w e present some constructive methods for obtaining perfect convex IaPelings of large classes of trees.

📜 SIMILAR VOLUMES

Forests of label-increasing trees

✍ John Riordan 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB

Label-increasing trees are fully labeled rooted trees with the restriction that the labels are in increasing order on every path from the root; the best known example is the binary case-no tree with more than two branches at the root, or internal vertices of degree greater than threeextensively exam

Group labelings of graphs

✍ Paul H. Edelman; Michael Saks 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 181 KB

## Abstract Given a graph Γ an abelian group __G__, and a labeling of the vertices of Γ with elements of __G__, necessary and sufficient conditions are stated for the existence of a labeling of the edges in which the label of each vertex equals the product of the labels of its incident edges. Such

Optimal Labellings of Rooted Directed Tr

Optimal Labellings of Rooted Directed Trees

✍ Jia-yu Shao 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 200 KB

We consider an optimal labelling problem for a rooted directed tree abbreviated . as ''RDT'' which is motivated by certain scheduling problem. We obtain several necessary and sufficient conditions for the optimal labellings of a RDT and give a polynomially bounded algorithm for constructing the opti

Total dominating functions in trees: Min

Total dominating functions in trees: Minimality and convexity

✍ E. J. Cockayne; C. M. Mynhardt; Bo Yu 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 380 KB

## Abstract A total dominating function (TDF) of a graph __G__ = (__V, E__) is a function __f__: __V__ ← [0, 1] such that for each __v__ ϵ V, Σ~uϵN(v)~ f(u) ≥ 1 (where __N__(__v__) denotes the set of neighbors of vertex __v__). Convex combinations of TDFs are also TDFs. However, convex combinations

On sequential labelings of graphs

✍ Thom Grace 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 276 KB

A valuation on a simple graph G IS an assignment of labels to the vertices of G which induces an assignment of labels to the edges of G. pvaluations, also called graceful labelings, and a-valuations, a subclass of graceful labelings, have an extensive literature; harmonious labelings have been intro

Bipartite labeling of trees with maximum

Bipartite labeling of trees with maximum degree three

✍ Bonnington, C. Paul; ?ir�?, Jozef 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB 👁 3 views

Let T = (V, E) be a tree with a properly 2-colored vertex set. A bipartite labeling of T is a bijection ϕ: V → {1, . . . , |V |} for which there exists a k such that whenever ϕ(u) ≤ k < ϕ(v), then u and v have different colors. The α-size α(T ) of the tree T is the maximum number of elements in the