Center of Trapezoid Graph: Application in Selecting Center Location to Set up a Private Hospital

Shaoli Nandi, Sukumar Mondal, Sovan Samanta (), Sambhu Charan Barman, Leo Mrsic and Antonios Kalampakas
Additional contact information
Shaoli Nandi: Department of Mathematics, Research Centre in Natural and Applied Sciences, Raja N. L. Khan Women’s College, Midnapore 721102, India
Sukumar Mondal: Department of Mathematics, Research Centre in Natural and Applied Sciences, Raja N. L. Khan Women’s College, Midnapore 721102, India
Sovan Samanta: Department of Mathematics, Tamralipta Mahavidyalaya, Tamluk 721636, India
Sambhu Charan Barman: Department of Mathematics, Shahid Matangini Hazra Government General Degree College for Women, Tamluk 721649, India
Leo Mrsic: Department of Technical Sciences, Algebra University, Gradiscanska 24, 10000 Zagreb, Croatia
Antonios Kalampakas: College of Engineering and Technology, American University of the Middle East, Egaila 54200, Kuwait

Mathematics, 2025, vol. 13, issue 5, 1-20

Abstract: The central location problem is a key aspect of graph theory, with a significant importance in various applications and studies within the field. The center of a graph is made up of nodes that have the smallest eccentricity, where eccentricity is defined as the greatest distance between a given node and any other node in the graph. To determine the graph’s center, it is essential to compute the eccentricity of each node. In this article, we explore various characteristics of the BFS tree of trapezoid graphs. We also present new properties that relate to the radius, diameter, and center of trapezoid graphs. For the trapezoid graph G , We prove that the difference between the d i a m e t e r ( G ) and the height of the BFS trees T t ( 1 ) , T t ( n ) , T t ( a ) , and T t ( b ) is at most one. We also establish relationship between r a d i u s ( G ) and d i a m e t e r ( G ) of trapezoid graphs. We also show that, to find the center of a trapezoid graph, it is not necessary to find the eccentricity of all vertices. Based on our studied results, we design an optimal algorithm for finding the center, radius, and diameter of trapezoid graphs. Also, we prove theoretically that our proposed algorithm compiles within O ( n ) time. We also find an algorithmic solution to real problems (that involves finding a center location in a district to build a private hospital that minimizes the farthest distance from it to all areas of the district) with the help of the trapezoid graph model and BFS trees within O ( n ) time.

Keywords: central nodes; trapezoid graph; BFS; algorithm; time complexity (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/5/885/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/5/885/ (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:13:y:2025:i:5:p:885-:d:1606963

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