Vertex Coloring and Eulerian and Hamiltonian Paths of Delaunay Graphs Associated with Sensor Networks

Manuel Ceballos () and María Millán
Additional contact information
Manuel Ceballos: Departamento de Ingeniería, Universidad Loyola Andalucía, Av. de las Universidades, s/n, 41704 Dos Hermanas, Sevilla, Spain
María Millán: Departamento de Ingeniería, Universidad Loyola Andalucía, Av. de las Universidades, s/n, 41704 Dos Hermanas, Sevilla, Spain

Mathematics, 2024, vol. 13, issue 1, 1-26

Abstract: In this paper, we explore the connection between sensor networks and graph theory. Sensor networks represent distributed systems of interconnected devices that collect and transmit data, while graph theory provides a robust framework for modeling and analyzing complex networks. Specifically, we focus on vertex coloring, Eulerian paths, and Hamiltonian paths within the Delaunay graph associated with a sensor network. These concepts have critical applications in sensor networks, including connectivity analysis, efficient data collection, route optimization, task scheduling, and resource management. We derive theoretical results related to the chromatic number and the existence of Eulerian and Hamiltonian trails in the graph linked to the sensor network. Additionally, we complement this theoretical study with the implementation of several algorithmic procedures. A case study involving the monitoring of a sugarcane field, coupled with a computational analysis, demonstrates the performance and practical applicability of these algorithms in real-world scenarios.

Keywords: algorithms; delaunay graph; sensor network; voronoi diagram; weighted graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/1/55/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/1/55/ (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:2024:i:1:p:55-:d:1554571

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