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

Prakash Veeraraghavan
Additional contact information
Prakash Veeraraghavan: Department of Computer Science and Information Technology, La Trobe University, Bundoora, VIC 3086, Australia

Mathematics, 2020, vol. 8, issue 11, 1-13

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 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.

Keywords: convexity; gcws; g-centroid; graph join; cartesian product; prism; corona (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/11/1927/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/11/1927/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:11:p:1927-:d:438768

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().