An Algorithm For Labeling A Tree
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Active In SP

Posts: 0
Joined: Jan 2009
05-10-2008, 04:34 PM



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


Important Note..!

If you are not satisfied with above reply ,..Please


So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  F5—A Steganographic Algorithm High Capacity Despite Better Steganalysis seminar ideas 0 516 19-04-2012, 11:34 AM
Last Post: seminar ideas
  Booth's Algorithm Example seminar paper 0 1,158 30-03-2012, 11:32 AM
Last Post: seminar paper
  LEAST MEAN SQUARE ALGORITHM projectsofme 1 2,382 18-04-2011, 12:16 PM
Last Post: pradeepkumarkaraka
  Bresenham Line Drawing Algorithm Circle Drawing & Polygon Filling project report helper 0 3,775 16-10-2010, 07:29 PM
Last Post: project report helper
  Statistical Algorithm for Power Transmission Lines Distance Protection seminar surveyer 0 994 13-10-2010, 10:57 AM
Last Post: seminar surveyer
  The Prediction Algorithm Based on Fuzzy Logic Using Time Series Data Mining Method seminar surveyer 0 1,853 13-10-2010, 10:15 AM
Last Post: seminar surveyer