Bipartite labeling of trees with maximum degree three
Bipartite labeling of trees with maximum degree three
复制标题
DOI：
10.1002/(sici)1097-0118(199905)31:1
复制
发表时间：
1999-05
期刊：
影响因子：
--
通讯作者：
C. Bonnington;J. Širáň
中科院分区：
文献类型：
--
作者：
C. Bonnington;J. Širáň
设T = （V， E）是一棵具有适当的2色顶点集的树。T的二部标记是一个双射φ: V威尼斯{1，…，|V|}，对于它存在一个k，使得当φ(u)≤k < φ(V)时，u和V具有不同的颜色。树T的α-size α(T)为集合{|φ(u) - φ(v)|中元素的最大个数；uv e}，接管了T的所有二部标记φ。量α(n)被定义为在所有有n个顶点的树上α(T)的最小值。在早先的一篇文章（J Graph Theory 19(1995), 201215）中，A. Rosa和第二作者证明了对于所有n≥4,5n-7≤α(n)≤(5n + 4)-6；上界被认为是(n)的渐近正确值。本文研究了最大次为3的树的α-大小问题。设α3(n)为所有有n个顶点的树中最小的α-大小，每个顶点最多为3度。我们证明了所有n≥12的α3(n)≥5n-6，从而支持上述信念。这个结果可以看作是对优美树猜想的近似，它表明n≥12个顶点且最大度为3的每棵树的“优雅大小”至少为5n-6。通过计算机搜索，我们还建立了对于所有n≤17的α3(n)≥n - 2。©1999 John Wiley & Sons, Inc图论[J]， 2007
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 sets {|φ(u) - φ(v)|; uv e E}, taken over all bipartite labelings φ of T. The quantity α(n) is defined as the minimum of α(T) over all trees with n vertices. In an earlier article (J Graph Theory 19 (1995), 201215), A. Rosa and the second author proved that 5n-7 ≤ α(n) ≤ (5n + 4)-6 for all n ≥ 4; the upper bound is believed to be the asymptotically correct value of (n). In this article, we investigate the α-size of trees with maximum degree three. Let α3(n) be the smallest α-size among all trees with n vertices, each of degree at most three. We prove that α3(n) ≥ 5n-6 for all n ≥ 12, thus supporting the belief above. This result can be seen as an approximation toward the graceful tree conjectureit shows that every tree on n ≥ 12 vertices and with maximum degree three has "gracesize" at least 5n-6. Using a computer search, we also establish that α3(n) ≥ n - 2 for all n ≤ 17. © 1999 John Wiley & Sons, Inc. J Graph Theory 31:715, 1999