La Trobe
1152058_Veeraraghaven,P_2020.pdf (356.57 kB)
Download file

The g-convexity and the g-centroids of composite graphs

Download (356.57 kB)
journal contribution
posted on 2021-01-20, 22:47 authored by Prakash VeeraraghavanPrakash Veeraraghavan
© 2020 by the author. Licensee MDPI, Basel, Switzerland. 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 N P-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.


Publication Date








Article Number



13p. (p. 1-13)





Rights Statement

The Author reserves all moral rights over the deposited text and must be credited if any re-use occurs. Documents deposited in OPAL are the Open Access versions of outputs published elsewhere. Changes resulting from the publishing process may therefore not be reflected in this document. The final published version may be obtained via the publisher’s DOI. Please note that additional copyright and access restrictions may apply to the published version.