On the class-reconstruction number of trees

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.