Taylor's Condition


For a given positive integer n, does there exist a weighted tree with n graph vertices whose paths have weights 1, 2, ..., (n; 2), where (n; 2) is a binomial coefficient? Taylor showed that no such tree can exist unless it is a perfect square or a perfect square plus 2. No such trees are known except n=2, 3, 4, and 6.

Székely et al. showed computationally that there are no such trees with n=9 and 11. They also showed that if there is such a tree on n vertices then the maximum vertex degree is at most (sqrt(8)/3+o(1))n and that there is no path of length larger than n/sqrt(2)(1+o(1)). They conjecture that there are only finitely many such trees.

See also

Golomb Ruler, Perfect Difference Set, Weighted Tree

Portions of this entry contributed by Adrian Riskin

Explore with Wolfram|Alpha


Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 56-60, 1985.Leech, J. "Another Tree Labeling Problem." Amer. Math. Monthly 82, 923-925, 1975.Székely, L. A. "Programs for Leech Tree of Nine Nodes and Eleven Nodes."ékely, L. A.; Wang, H.; and Zhang, Y. "Some Non-Existence Results on Leech Trees." Bull. Inst. Combin. Appl. 44, 37-45, 2005.Taylor, H. "Odd Path Sums in an Edge-Labeled Tree." Math. Mag. 50, 258-259, 1977.

Referenced on Wolfram|Alpha

Taylor's Condition

Cite this as:

Riskin, Adrian and Weisstein, Eric W. "Taylor's Condition." From MathWorld--A Wolfram Web Resource.

Subject classifications