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

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

Download (356.57 kB)
journal contribution
posted on 20.01.2021, 22:47 by Prakash 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.

History

Publication Date

02/11/2020

Journal

Mathematics

Volume

8

Issue

11

Article Number

1927

Pagination

13p. (p. 1-13)

Publisher

MDPI

ISSN

2227-7390

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.