Perfect distance forests

about the previous topic for perfect distance forests, two references that might be helpful for anyone interested,

References:

[1] B.Calhoun, J. Polhill, Perfect distance forests, Australian Journal of Combinatorics, vol. 42(2008), p. 211-222.(NOT AVAILABLE ONLINE)

[2] W.Calhoun, K. Ferland, L. Lister and J. Polhill, Minimal distinct distance trees, J.Combin. Math. Combin. Computing vol. 61(2007) p. 33-57.(AVAILABLE HERE)

so leech trees of order 6 or smaller are known. For order 9,11 or 16 there no Leech trees either leaving 18 the smallest open case. Szekely has conjectured that no additional Leech trees exist but this is still open. Another generalization can be studied in a different domain, $Z_{n}$ .

Let be a tree of $n$ vertices and let $k = \left(\begin{array}{c} n \\ 2 \end{array} \right) +1$ . We say that is a modular Leech tree if there exists an edge weighting function $w: E(T) \rightarrow Z_{k}$ such that each of the paths within has a distinct weight from with the sums taken modulo $k$ . 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 perfect distance tree as defined previously of order $n$ is also a modular Leech tree over $Z_{ \left(\begin{array}{c} n \\ 2 \end{array} \right) +1}$ in which none of the path sums, before applying the mod operation, have a weight greater than $\left(\begin{array}{c} n \\ 2 \end{array} \right)$ . Thus Leech’s original five examples provide us with five modular Leech trees. For more read here.

A nice problem that was posted here and was proposed in ARMO at 1986 asked:

PROBLEM: The governor of a kingdom wants to construct in it $n$ cities and $n-1$ roads between them so that one can travel from any city to any other one. (Every road connects two cities, the roads do not intersect and do not pass through other cities). The governor also wants the shortest distances between any two cities in the road network to be equal to $1,2,...,n(n-1)/2$ km.

Is this possible for a) $n=6$ , b) $n=1986$ ?

These trees are called perfect distance trees. There are not many. One can try by trial and error for n=2 until the case for n=6. These cases are shown below (fig. 1). They are also called Leech trees due to the man that first asked for their existence in 1975.

Fig. 1: All known Perfect distance Trees.

A basic result for investigating perfect distance trees and the generalization to all graphs, is Taylor’s criterion:

Taylor theorem: Suppose that T is a perfect distance tree on order n. Then there exists an integer $k$ such that, $n=k^2+2$ .

In [1] the generalization for a graph $G$ with $k$ components of order $n_{i}$ respectively starts with the definitions of edge-labelling,distance between two vertices of the same component, distinct distance labelling, distinct distance graph. A perfect distance graph $G$ is a distinct distance tree whose maximum distance is the number of pairs of distinct vertices in $G$ such that two vertices are in the same component of $G$ . We denote this maximum distance as $(G,\lambda)=\sum_{i=1}^{k}\begin{pmatrix} n_{i}&\\ 2&\end{pmatrix}$ . A Taylor colouring is defined as a function $t: V \rightarrow {0,1}$ , where $V$ is the number of vertices of $G$ , such that if $x$ and $y$ are in the same component of $G$ then: $d(x,y)= |t(x) - t(y)|(mod2)$ . Moreover it is defined that:

$n_{i,j} = | \{ x: x$ belongs to the $i-th$ component and $t(x)=j \}$ , for $j=0,1$ . The next theorem is the first generalization of leech trees:

Theorem: (Generalized Taylor’s Condition). If $G(,\lambda)$ is an n-vertex perfect distance graph with $k$ components and a Taylor labelling, then there are non-negative integers $a_{1},a_{2},...,a_{k}$ such that : $a_{i}=n_{i}(mod2)$ and $a_{i}\leq n_{i}$ for $1,2,...,k$ such that,

$a_{1}^{2}+a_{2}^{2}+...+a_{k}^{2}+2p=n$ where p=maxdist(G,\lambda)mod2. It is also true that: $a_{i}=|n_{i,0}-n_{i,1}|$ .

I will not provide the proof since it is on [2] which is not available online.

Perfect Distance Forests

Some more interesting results that arise from the above theorem is for forests with the same number of components. If the components are the $K_{1,2}$ then we have,

Fact 1: $kK_{1,2}$ can be labelled as a perfect distance forest if and only if $k\equiv0,1 (mod4)$ .

Examples are found in fig. 2,

FIg. 2: Examples for $4 K_{1,2}$ and $5K_{1,2}$

Fact 2: $kK_{1,3}$ can be labelled as a perfect distance forest $k$ .

Example algorithm for fixing $kK_{1,3}$ from $kK_{1,2}$ is shown also in [1] (fig. 3)

Fig. 3: Fixing $kK_{1,3}$ from $kK_{1,2}$

Finally special reference is done for forests with 2 components. The previous theorems help to rule out trivial cases for some number of vertices. In figure 4 there are all the perfect distance forests with two component for $11\leq n \leq 17$ ,

$Fig. 4: All the perfect distance forests with two component for $latex 11\leq n \leq 17$.$

Refereces:

[1] B.Calhoun, J. Polhill, Perfect distance forests, Australian Journal of Combinatorics, vol. 42(2008), p. 211-222.

[2] W.Calhoun, K. Ferland, L. Lister and J. Polhill, Minimal distinct distance trees, J.Combin. Math. Combin. Computing vol. 61(2007) p. 33-57.

zeracuse

science , humor and other geek things …

Tag Archives: Perfect distance forests

perfect distance trees-graphs-forests. An old but beautiful problem in weighted graphs !