𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bipartite labelings of trees and the gracesize

✍ Scribed by Alexander Rosa; Jozef Širáň

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
681 KB
Volume
19
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let T = (V, E) be a tree whose vertices are properly 2‐colored. A bipartite labeling of T is a bijection f: V ← {0, 1, ⃛, | E |} for which there is a k such that whenever f(u) ≤ k < f(v), then u and v have different colors. The α‐size of the tree T is the maximum number of distinct values of the induced edge labels |f(u) ‐ f(v)|, uv ϵ E, taken over all bipartite labelings f of T.

We investigate the asymptotic behavior of the α‐size of trees. Let α(n) be the smallest α‐size among all the trees with n edges. As our main result we prove that 5(n + 1)/7 ≤ α(n) ≤ (5__n__ + 9)/6. A connection with the graceful tree conjecture is established, in that every tree with n edges is shown to have “gracesize” at least 5__n__/7. © 1995 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Convex labelings of trees
Convex labelings of trees
✍ Stephen J. Dow; Douglas F. Rall; Peter J. Slater 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 456 KB

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

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

Permanent of the Laplacian matrix of tre
Permanent of the Laplacian matrix of trees and bipartite graphs
✍ Richard A Brualdi; John L Goldwasser 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 805 KB

be the Laplacian matrix of G. When G is a tree or a bipartite graph we obtain bounds for the permanent of L(G) both in terms of n only and in terms of d 1 ..... d,. Improved bounds are obtained in terms of the diameter of T and the size of a matching in T.