The centroidal branches of a separable graph are edge reconstructible

✍ Scribed by Robert Molina

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 660 KB
• Volume: 179
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(97)00032-0

✦ Synopsis

If T is a tree, then the weight of a vertex v in T is the number of vertices in a largest component of T -v. The centroid of a tree is the set of vertices of minimum weight. We show that if G is a separable graph then there is a unique block or cutvertex that contains the centroids of all spanning trees of G. We define this block or cutvertex to be the centroid of G. We show that the centroid and rooted branches of the centroid are edge reconstructible, that is, determined up to isomorphism by the set of edge-deleted subgraphs.