Almost all trees are almost graceful
Almost all trees are almost graceful
复制标题
几乎所有的树木都近乎优雅
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
J. Hladký
中科院分区：
文献类型：
--
作者：
Anna Adamaszek;Peter Allen;C. Grosu;J. Hladký
1967年ROSA的优美树猜想断言n阶树T的顶点可以用数{1，2，…来内射标号，n}，使得在边缘上引起的绝对差值是成对不同的。我们证明了对每个γ>；0和对所有n>；n0(γ)猜想的下列放宽。假设(I)T的最大次数由Oγ(n/logn)有界，以及(Ii)顶点标号选自集合{1，2，…，⌈(1+γ)n⌉}。然后是V(T)的内射标号，使得边上的绝对差是两两不同的。特别地，几乎所有n个顶点上的树都渐近地承认这样的标号。证明通过显示某种非常自然的随机化算法以高概率产生所需的标记来进行。
The Graceful Tree Conjecture of Rosa from 1967 asserts that the vertices of each tree T of order n can be injectively labeled by using the numbers {1,2,…,n} in such a way that the absolute differences induced on the edges are pairwise distinct. We prove the following relaxation of the conjecture for each γ>0 and for all n>n0(γ). Suppose that (i) the maximum degree of T is bounded by Oγ(n/logn ), and (ii) the vertex labels are chosen from the set {1,2,…,⌈(1+γ)n⌉}. Then there is an injective labeling of V(T) such that the absolute differences on the edges are pairwise distinct. In particular, asymptotically almost all trees on n vertices admit such a labeling. The proof proceeds by showing that a certain very natural randomized algorithm produces a desired labeling with high probability.
影响因子：
1.7
作者：
Allen P
通讯作者：
Allen P