On the g-centroidal problem in special classes of perfect graphs

In this paper we prove some basic properties of the g-centroid of a graph defined through g-convexity. We also prove that finding the g-centroid of a graph is NP-hard by reducing the problem of finding the maximum clique size of G to the g-centroidal problem. We give an O(n2) algorithm for finding the g-centroid for maximal outer planar graphs, an O(m + nlogn) time algorithm for split graphs and an O(m2) algorithm for ptolemaic graphs. For split graphs and ptolemaic graphs we show that the g-centroid is in fact a complete subgraph.