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

Abstract

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 G1 and G2, 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 G1 and G2. We also characterize the structure of the g-centroid under various cases. For the Cartesian product of G1 and G2 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.

Keywords

• convexity
• gcws
• g-centroid
• graph join
• cartesian product
• prism