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(n^2)\) algorithm for finding the \(g\)-centroid for maximal outer planar graphs, an \(O(m + n\log n)\) time algorithm for split graphs and an \(O(m^2)\) algorithm for ptolemaic graphs. For split graphs and ptolemaic graphs we show that the \(g\)-centroid is in fact a complete subgraph.