On The $g$-centroidal Problem in Special Classes of Perfect Graphs

Abstract

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.