jcn@aplvax.UUCP (06/09/83)
This problem deals strictly with tree graphs. Define a "distance sequence" as a sequence of numbers that are the distances between all unique pairs of leaves in a tree (leaves are points of degree 1). For example, the distance sequence for a tree with 2 points is <1>, while the distance sequence for the tree with 3 points is <2>, the distance sequence for the star graph 4 points is <2,2,2>. The question: If two trees have the same distance sequence, must they be automorphic (i.e. the same tree)? That is, does a distance sequence uniquely define a tree? John Noble Johns Hopkins Applied Physics Lab Laurel, Md 20707 ...rglvax!umcp-cs!aplvax!jcn ...decvax!harpo!seismo!umcp-cs!aplvax!jcn
ljdickey@watmath.UUCP (Lee Dickey) (06/27/83)
About a week or so ago, I passed along an example of two graphs that had the
same set of leaf distances, but which were not isomorphic. Here is another pair
of graphs, discovered to Prof. J. Michael Robinson, smaller than the previous
example, which have that same property:
o o
| |
o------------o o------------o
| / \ | / \
o o o o o o
/ \ | | / \ | |
o o o o o o o o
Each of these graphs has:
1 pair of leaves with distance 2
2 pairs of leaves with distance 3
3 pairs of leaves with distance 4
4 pairs of leaves with distance 5.
Prof. Ronald C. Read has discovered the smallest (counting the number of
vertices) example of a pair of graphs that have the same
distance sequences, but which are not isomorphic:
o o o o o
\ / \|/
o--o--o o
| |
o o
/ \ |
o o o
/ \ /|\
o o o o o
Each of these graphs has:
6 pairs of leaves with distance 2
9 pairs of leaves with distance 4.
It is interesting to note that they have different numbers of vertices.