The G-Convexity and the G-Centroids of Composite Graphs

The graph centroids defined through a topological property of a graph called g-convexity found its application in various fields. They have classified under the “facility location” problem. However, the g-centroid location for an arbitrary graph is NP -hard. Thus, it is necessary to devise an approximation algorithm for general graphs and polynomial-time algorithms for some special classes of graphs. In this paper, we study the relationship between the g-centroids of composite graphs and their factors under various well-known graph operations such as graph Joins, Cartesian products, Prism, and the Corona. For the join of two graphs G 1 and G 2 , the weight sequence of the composite graph does not depend on the weight sequences of its factors; rather it depends on the incident pattern of the maximum cliques of G 1 and G 2 . We also characterize the structure of the g-centroid under various cases. For the Cartesian product of G 1 and G 2 and the prism of a graph, we establish the relationship between the g-centroid of a composite graph and its factors. Our results will facilitate the academic community to focus on the factor graphs while designing an approximate algorithm for a composite graph.