20th All Soviet Math Olympiad

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: 20th All Soviet Math Olympiad

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