AN ALGORITHM FOR LABELING A TREE

KOH KHEE MENG AND TAY ENG GUAN

Abstract. An algorithm is described for labeling the vertices of a tree. A tree can then be determined by the collection of labels of its vertices, listed in lexicographic order.


1. Introduction

The notion of distance degree sequences of graphs was studied by Randic [3] for the purpose of distinguishing chemical isomers by their graph structures. Other sequences for this purpose have also been proposed and discussed. The objective and hope is to develop an index which would be useful both for the ?graph isomorphism problem?, i.e. how to determine if two given graphs are isomorphic or not, and to predict various properties of the molecule at hand.

Randic [3] conjectured that a tree is determined by its distance degree sequence and verified it for all trees with 14 or fewer vertices. Slater [5] disproved this conjecture by showing how to construct an infinite class of pairs of trees so that each pair has the same distance degree sequence.

It is known that the graph isomorphism problem when restricted to trees belongs to P, the class of all problems that can be solved by a polynomial time algorithm. Neville [2] devised a coding technique that could encode a labeled tree with n vertices in a row of n?2 symbols. Other than the degrees of vertices, the coding does not contain much information about the structure of the tree. On the other hand, Read [4] obtained a binary code for unlabeled trees which had many useful properties. However, the length of the code for a tree with n vertices was approximately of the order 2n and so would present some problems for handling, even by a computer. It was suggested by Read that the algorithm could be carried out using integer arithmetic instead of the manipulation of binary strings. Both the codings of Neville and Read are of polynomial time. In this paper, we present a new polynomial time algorithm to solve the graph isomorphism problem for unlabeled trees. We do this by defining an efficient algorithm for labeling a tree. A tree T can then be determined by the sequence, in lexicographic order, of labels of its vertices which we shall call the vertex label sequence of T. For a tree with n vertices, the vertex label sequence consists of at most n2 symbols. The labels assigned to the vertices also have some interesting properties. For chemists however, it remains to be seen if a suitable index which can predict the physical and chemical properties of a compound can be obtained from the unique vertex label sequence.
Let G be a (simple) graph with vertex set V(G). For u, v ? V(G), let dG(u, v) denote the distance between u and v in G. The eccentricity eG(v) of v is defined as eG(v) = max {dG(v, x) | x ? V(G)}, and the diameter d(G) of G is defined by d(G) = max {eG(v) | v ? V(G)} = max{dG(u, v) | u, v ? V(G)}. We shall denote by NG(v) the set of vertices adjacent to v in G, and by degG(v) (= |NG(v)|) the degree of v in G. The subscript G is omitted if there is no danger of ambiguity.

For each k = 1, 2, ?, m, let (k) = (k1, k2, ?, kf(k)) be a finite sequence of nonnegative integers. The sequence of m sequences <(1), (2), ?, (m)> is said to be in lexicographic order if whenever i < j, either ?there exists r such that ir < jr and is = js for all s < r? or ?is = js for all s with 1 ? s ? f(i) and f(i) ? f(j)?. The sequence <(1), (2), ?, (m)> is said to be in reverse lexicographic order if the sequence <(m), (m?1), ?, (1)> is in lexicographic order.

For a vertex v in G and a nonnegative integer i, let di(v) denote the number of vertices u such that d(v, u) = i. Thus d0(v) = 1 and d1(v) = deg(v). The distance degree sequence of v, denoted by dds(v), is the sequence defined by dds(v) = (d0(v), d1(v), d2(v), ?, de(v)(v)). The distance degree sequence of G, denoted by dds(G), is the sequence, in lexicographic order, of sequences dds(v), where v ? V(G).


For More Visit

HERE