Some properties of graph centroids (Q1179740)

Let \(G=(V,E)\) be a graph. A path \(P\) in \(G\) is said to be chordless if the only pairs of vertices on \(P\) that are adjacent in \(G\) are consecutive along \(P\). A set \(S\) of vertices is said to be convex if \(S\) contains every vertex on every chordless path between vertices in \(S\). The weight of a vertex \(u\in V\) is denoted by \(w(u)=\max\{| S|\mid u\in S\) and \(S\in{\mathcal C}\}\) where \(\mathcal C\) is the family of convex subsets of \(V\). Then, the centroid of \(G\) is defined to be the subgraph of \(G\) induced by vertices with the smallest weight. This paper provides some necessary and sufficient conditions for a graph to be a centroid of another graph even itself. Applications of the results to some particular classes of graphs such as chordal Halin and series- parallel are also discussed.