Vertex Coloring and Eulerian and Hamiltonian Paths of Delaunay Graphs Associated with Sensor Networks
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 focu...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-12-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/13/1/55 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841549158775783424 |
|---|---|
| author | Manuel Ceballos María Millán |
| author_facet | Manuel Ceballos María Millán |
| author_sort | Manuel Ceballos |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-8e3aeaebbe9e48d5ac5edaf57e9005aa |
| institution | Kabale University |
| issn | 2227-7390 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj-art-8e3aeaebbe9e48d5ac5edaf57e9005aa2025-01-10T13:18:06ZengMDPI AGMathematics2227-73902024-12-011315510.3390/math13010055Vertex Coloring and Eulerian and Hamiltonian Paths of Delaunay Graphs Associated with Sensor NetworksManuel Ceballos0María Millán1Departamento de Ingeniería, Universidad Loyola Andalucía, Av. de las Universidades, s/n, 41704 Dos Hermanas, Sevilla, SpainDepartamento de Ingeniería, Universidad Loyola Andalucía, Av. de las Universidades, s/n, 41704 Dos Hermanas, Sevilla, SpainIn 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.https://www.mdpi.com/2227-7390/13/1/55algorithmsdelaunay graphsensor networkvoronoi diagramweighted graph |
| spellingShingle | Manuel Ceballos María Millán Vertex Coloring and Eulerian and Hamiltonian Paths of Delaunay Graphs Associated with Sensor Networks Mathematics algorithms delaunay graph sensor network voronoi diagram weighted graph |
| title | Vertex Coloring and Eulerian and Hamiltonian Paths of Delaunay Graphs Associated with Sensor Networks |
| title_full | Vertex Coloring and Eulerian and Hamiltonian Paths of Delaunay Graphs Associated with Sensor Networks |
| title_fullStr | Vertex Coloring and Eulerian and Hamiltonian Paths of Delaunay Graphs Associated with Sensor Networks |
| title_full_unstemmed | Vertex Coloring and Eulerian and Hamiltonian Paths of Delaunay Graphs Associated with Sensor Networks |
| title_short | Vertex Coloring and Eulerian and Hamiltonian Paths of Delaunay Graphs Associated with Sensor Networks |
| title_sort | vertex coloring and eulerian and hamiltonian paths of delaunay graphs associated with sensor networks |
| topic | algorithms delaunay graph sensor network voronoi diagram weighted graph |
| url | https://www.mdpi.com/2227-7390/13/1/55 |
| work_keys_str_mv | AT manuelceballos vertexcoloringandeulerianandhamiltonianpathsofdelaunaygraphsassociatedwithsensornetworks AT mariamillan vertexcoloringandeulerianandhamiltonianpathsofdelaunaygraphsassociatedwithsensornetworks |