Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/111502
Title: | On the class-reconstruction number of trees |
Authors: | Harary, Frank Lauri, Josef |
Keywords: | Graph theory Mathematics Graphic methods |
Issue Date: | 1988 |
Publisher: | Oxford University Press |
Citation: | Harary, F., & Lauri, J. (1988). On the class-reconstruction number of trees. The Quarterly Journal of Mathematics, 39(1), 47-60. |
Abstract: | ALL graphs considered are finite and undirected. We shall mostly follow the standard graph theoretic terminology of [2], the most notable exception being that here we use the terms vertex and edge instead of point and line respectively. We also require some definitions and notation not found in [2]. For any graph G, the sets of vertices and of edges will be denoted by V = V(G) and E = E(G) respectively. The number of vertices of G is called the order of G and is denoted by n( G). Two adjacent vertices are said to be neighbours. As in [2], two vertices u, v are similar if there exists some automorphism f on G such that f(u) = v; they are removal-similar if G - u and G - v are isomorphic, and they are pseudosimilar if they are removal-similar but not similar. Henceforth, T will always denote a tree. A cutvertex of T is an end-cutuertex if, with at most one exception, all of its neighbours are endvertices. The weight of a vertex v of T is the maximum order of a component of T - v: it is denoted by wt ( v ). The centroid of T is then the set of vertices with minimum weight. This minimum weight is called the weight of T, and is denoted by wt (T). It is well-known that the centroid of T contains either just one vertex (unicentroidal tree) of else two adjacent vertices (bicentroidal tree). A vertex in the centroid is called a centroidal vertex. Finally, let v be an endvertex of T adjacent to x. If there is another vertex y * x in T such that the tree T - vx + vy ( obtained from T by removing edge vx and adding vy) is isomorphic to T, then v is called a replaceable vertex of T. An endvertex of T which is not replaceable is said to be irreplaceable. |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/111502 |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
On_the_class_reconstruction_number_of_trees_1988.pdf Restricted Access | 354.75 kB | Adobe PDF | View/Open Request a copy |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.