# Modular Leech Trees of Order at Most 8

Authors: David Leach
Journal: International Journal of Combinatorics
 (2014)

---

## Abstract

In 1975, John Leech asked when can the edges of a tree onn vertices be labeled with positive integers such that the sums along the paths are exactly the integers 1
,
2
,
…
,
n
2. He found five such trees, and no additional trees have been discovered since. In 2011 Leach and Walsh  introduced the idea of labeling trees with elements of the group Z
k where k
=
n
2
+
1 and examined the cases for n
≤
6. In this paper we show that no modular Leech trees of order 7 exist, and we find all modular Leech trees of order 8.


---

## Body

## 1. Introduction

A tree onn vertices is said to be aLeech tree if its edges can be weighted with positive integers in such a way that each of the (
n
2
) paths has a distinct weight from the set {
1,2
,
…
,
(
n
2
)
}. The weight of a path is found by summing all of its edge weights. Leech [1] found the five examples shown in Figure 1, which are to date the only ones known. In 1977, Taylor [2] proved that, in order for a Leech tree of order n to exist, it must be that n
=
k
2 or n
=
k
2
+
2 for some integer k. Since then it has been shown by several authors [3–5] that no Leech trees of order 9, 11, or 16 exist, leaving n
=
18 as the smallest open case. Székely et al. [4] have conjectured that no additional Leech trees exist. Since Leech trees are so difficult to come by, we consider the generalization to modular Leech trees.Figure 1
The five known Leech trees.LetT be a tree on n vertices and let k
=
(
n
2
)
+
1. We say that T is amodular Leech tree if there exists an edge weighting function w
:
E
(
T
)
→
Z
k such that each of the (
n
2
) paths within T has a distinct weight from 1,2
,
…
,
(
n
2
) with the sums taken modulo (
n
2
)
+
1. We call such an edge weighting function a Z
k
-Leech labeling. Since the pathweights are all distinct, the function w induces a bijection between the paths of T and the elements of the group Z
k. We use w to refer to this bijection as well.Note that a “normal” Leech tree of ordern is also a modular Leech tree over Z
(
n
2
)
+
1 in which none of the path sums, before applying the mod operation, have a weight greater than (
n
2
). Thus Leech’s original five examples provide us with five modular Leech trees. The only other example previously known is the tree of order 6 found in [6] shown in Figure 2. It was also shown in [6] that no modular Leech tree of order 5 exists.Figure 2
Leech tree of order6 over Z
16.In Section2 we will see how Taylor’s condition applies to modular Leech trees, and in Section 3 we will enumerate all Leech trees of order at most 8.


## 2. Taylor’s Condition for Modular Leech Trees

For the normal Leech trees, Taylor’s condition restricts the possible orders severely. However, with modular Leech trees overZ
k, Taylor’s condition only applies when k is even. The proof is very similar to half of Taylor’s proof.Theorem 1.
Suppose thatT is a modular Leech tree of order n and n
≡
2 or 3 (mod
⁡ 4); then n
=
m
2
+
2 for some integer m.Proof.
Assume thatT is a modular Leech tree of order n and that n
≡
2 or 3 (mod 4). Since n
≡
2 or 3 (mod 4), we have that (
n
2
) is odd and thus the modulus (
n
2
)
+
1 is even.
We color each vertex of the tree black or white as follows: start at any vertexv and color it black. From v we color all other vertices by traversing the edges of the graph. We keep the same color across edges with even weight and change colors across edges with odd weight. When all vertices are colored, an edge connects different colored vertices if and only if its weight is odd. Furthermore, since the modulus is even, for any vertices u
,
v
∈
V
(
T
), the path from u to v has odd weight if and only if u and v are colored with opposite colors.
Now we count the number of odd paths in two ways: letb and w be the number of black and white vertices, respectively. Thus the number of odd paths is b
w. Also, since there are (
n
2
) paths and (
n
2
) is odd, the number of odd paths is (
1
/
2
)
(
(
n
(
n
-
1
)
/
2
)
+
1
). Putting these together gives n
-
2
=
n
2
-
4
b
w. Substituting b
+
w for n on the right side leads to n
=
(
b
-
w
)
2
+
2 and the theorem is proved.The proof of Theorem1 makes use of the fact that, under the assumptions of the theorem, a path has odd weight if and only if it contains an odd number of odd-weight edges. This fact does not hold when the modulus is odd. (For example, consider a path on four vertices with edges weighted 3, 5, and 1 and examine the path-weights mod 7.) Recall that a normal Leech tree on n vertices is also a modular Leech tree over Z
k where k
=
(
n
2
)
+
1 and by Taylor’s condition n
=
m
2 or m
2
+
2 for some integer m. We can conclude the following.Theorem 2.
If there exists a modular Leech tree of ordern, and n is not m
2
+
2 for some integer m, then n
≡
0 or 1 (mod
⁡ 4).


## 3. Computational Results

We have already seen modular Leech trees of orders 2, 3, 4, and 6. By Leach and Walsh [6] and Theorem 2 we know that none exist for 5 or 7. To examine larger values of n, we use computer search. The following theorem and corollary reduce the space that must be searched.Theorem 3.
Letn be an integer and k
=
(
n
2
)
+
1. Suppose that f
:
E
(
T
)
→
Z
k is a Z
k-Leech labeling of a tree T. Then for any b
∈
Z
k satisfying g
c
d
(
b
,
k
)
=
1, the function g
:
E
(
T
)
→
Z
k defined by g
(
e
)
=
b
·
f
(
e
) is also a Z
k-Leech labeling of T.Proof.
LetP
(
T
) be the set of all paths in T. We can consider f as a bijection between P
(
T
) and Z
k, so for every nonzero b
∈
Z
k, there exists a path with weight b. Now define g
:
P
(
T
)
→
Z
k by g
(
e
)
=
b
·
f
(
e
).
We now show thatg
:
P
(
T
)
→
Z
k is bijective: let P
1 and P
2 be paths in T and suppose that g
(
P
1
)
=
g
(
P
2
). Then b
·
f
(
P
1
)
=
b
·
f
(
P
1
). Since g
c
d
(
b
,
k
)
=
1, b
-
1 exists and thus f
(
P
1
)
=
f
(
P
2
). Since f is a bijective, P
1
=
P
2 and thus g is also bijective. Since g
:
P
(
T
)
→
Z
k is bijective, g is a Leech labeling of T.Corollary 4.
If there exists aZ
k-Leech labeling of a tree T and e
∈
E
(
T
), then there exists a Z
k-Leech labeling of T in which edge e has weight 1.Forn
=
8, there are 23 distinct unlabeled trees. By computer search, we find that there is one modular Leech tree for n
=
8 and the edge-weighting function is unique, up to group and graph isomorphism. It is shown in Figure 3.Figure 3
Leech tree of order8 over Z
29.



---

*Source: 218086-2014-09-18.xml*