Some properties of graph centroids

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.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Some properties of graph centroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1179740)