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

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 cities and 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 km.

Is this possible for a) , b) ?

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 such that, .

In [1] the generalization for a graph with components of order 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  is a distinct distance tree whose maximum distance is the number of pairs of distinct vertices in such that two vertices are in the same component of . We denote this maximum distance as . A Taylor colouring  is defined  as a function , where is the number of vertices of , such that if  and  are in the same component of  then: . Moreover it is defined that:

belongs to the component and , for . The next theorem is the first generalization of leech trees:

Theorem: (Generalized Taylor’s Condition). If is an n-vertex perfect distance graph with components and a Taylor labelling, then there are non-negative integers  such that :  and  for  such that,

where p=maxdist(G,\lambda)mod2. It is also true that: .

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 then we have,

Fact 1:  can be labelled as a perfect distance forest if and only if .

Examples are found in fig. 2,

FIg. 2: Examples for and

Fact 2: can be labelled as a perfect distance forest  .

Example algorithm for fixing from is shown also in [1] (fig. 3)

Fig. 3: Fixing from

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 ,

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.

graph distances, paths and other ideas …

The graph geodesics is a shortest path between two graph vertices of a graph. There may be more than one different shortest paths, all of the same length. Graph geodesics may be found using an existing famous algorithms such as: breadth-first traversal or Dijkstra’s algorithm.

The graph distance between two vertices denoted with is the length of the shortest, or minimal, path between them. (The notion of distance applies only to connected components of graphs see figure 1).

The graph diameter of a graph is the longest distance you can find in the graph. It is a measure of the length of the longest minimal path. (A path is not minimal if the two vertices at its endpoints could be connected by a shorter path). So the length of the maximum geodesic in a given graph is called the graph diameter, and the length of the minimum geodesic is called the graph radius.

The diameter of a graph stands the same way in Euclidean geometry (where the diameter of the circle is the largest distance inside a circle between any two points). Consider now the graph radius as the distance from the center to the outer edge. We can stretch and bend this concept into that of the radius of a graph.

The eccentricity of a vertex is the length of the longest minimal path from that vertex to some vertex in the graph. You can think of the eccentricity of a vertex as the longest distance in the graph from there to somewhere (see figure 2).

The graph center of a graph is the collection of vertices (called the central vertices) whose eccentricity is least. In other words, it’s the collection of vertices whose longest distance to all other vertices is the smallest.

The graph radius of a graph is the length of the shortest eccentricity in the graph. It’s the eccentricity of each central vertex.

Now the inspiration problem of the day is from an old russian graph theory problem that askes:

Problem: Given n points can one build n-1 roads, so that each road joins two points, the shortest distance between any two points along the roads belongs to {1, 2, 3, … , n(n-1)/2 }, and given any element of {1, 2, 3, … , n(n-1)/2 } one can find two points such that the shortest distance between them along the roads is that element? a) for n=6, b) for n=1986.

Is there a mistake in Vasiliev & Egorov’s book?

In All Soviet Mathematics Olympiad of 1980 the following problem was proposed for grades 9-10 at day 1 (problem 3):

PROBLEM:There are several settlements around Big Lake. Some pairs of settlements are directly connected by a regular shipping service. For all A  , settlement A is directly connected to X iff B is not directly connected to Y, where B is the next settlement to A counterclockwise and Y is the next settlement to X counterclockwise. Show that you can move between any two settlements with at most 3 trips.

The official solution (there are two solutions) follow the rule that: if A,B,C are three settlements that are placed counterclockwise, then A and B are directly connected via a ship route iff B and C do not.

So there are two possibilities: either the problem statement is wrong or the statement is correct but the solution is missing something. Notice that the formal statement of the problem is the following:

PROBLEM:на берегу круглого озера расположено несколько пунктоь между некоторыми из них устаовлено теплхоаное сообщение. известо, что два пункта а и в связаны рейсом тогда  и то́лько тогда, когда следующие за ними справа по берегу два пункта  а’ и в’ рейсом не связаны. докажите, что ие любого пункта в  любой другой пункт можно добратся теплоходом, причем не более чем с двумя пересадками

which is basically the above English statement.

try to construct a working algorithm. It’s hard

In general there certain methods that (almost) always work and give nice solution in maths,engineering. For example take the method of trial and error. In my case for Graph theory problems these are:

1) Induction

2) Add/delete a node and figure out what is the logical flaw

3) Search using the concepts of minimum and maximum (usually gives beautiful solution)

4) Construct and algorithm

For me number 4 is really hard and this demands many  time and work. A good application must have a criterion that is applied recursively in every partition of the sets that occur each time. The procedure must stop after some steps and we have to be sure that this happens. The condition must be chosen properly so that it defines an equivalence relation

Partitioning a set of vertices with a condition related to the problem.

Anyway, the problem that inspired me for this thought (and applied successfully both 3) and 4) )  was the following:

Problem: Given points, show that you can place an arrow between each pair of points, so that given any point you can reach any other point by travelling along either one or two arrows in the direction of the arrow.

a non-binary tree with different leaves

A triangle table is built according to the rule: You put the natural number in the upper row, and then You write under the number from the left side , and from the right side  . For example, if , You get the table on the picture below.
Prove that all the numbers on each particular line are different.

        2
       / \
     /     \
    4       3
  /  \     /  \
 16   5   9    4
/ \  / \ / \  / \

this is perhaps one of the coolest problems in graph theory I met so far. The problem states:

PROBLEM: There is a flu epidemic in elf city. The course of the disease is always the same. An elf is infected one day, he is sick the next, recovered and immune the third, recovered but not immune thereafter. Every day every elf who is not sick visits all his sick friends. If he is not immune he is sure to catch flu if he visits a sick elf. On day 1 no one is immune and one or more elves are infected from some external source. Thereafter there is no further external infection and the epidemic spreads as described above. Show that it is sure to die out (irrespective of the number of elves, the number of friends each has, and the number infected on day 1). Show that if one or more elves is immune on day 1, then it is possible for the epidemic to continue indefinitely. (All Russian Math Olympiad 1980)

As a first hint one shall think, what is really the difference of the following two graphs?

tree (no-cycle)

a cycle exists