Geodesic Dominated Coloring of Graphs
In this paper, we introduce geodesic dominated coloring, a novel variant of dominated coloring in graphs, where each color class is dominated by at least one geodesic. This concept builds upon the classical dominated coloring framework, offering fresh perspectives on vertex domination and graph colo...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10890956/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850078517082980352 |
|---|---|
| author | M. Paruvatha Vathana R. Jayagopal |
| author_facet | M. Paruvatha Vathana R. Jayagopal |
| author_sort | M. Paruvatha Vathana |
| collection | DOAJ |
| description | In this paper, we introduce geodesic dominated coloring, a novel variant of dominated coloring in graphs, where each color class is dominated by at least one geodesic. This concept builds upon the classical dominated coloring framework, offering fresh perspectives on vertex domination and graph coloring. We begin by examining the intricate relationships between domination parameters closely linked to geodesic dominated coloring, emphasizing their connections, contrasts, and the transfer of hereditary properties. To motivate this study, we highlight the significance of geodesic dominated coloring and its potential applications across diverse domains. We establish key foundational results, including lower bounds for the geodesic dominated chromatic number, to provide deeper insights into this innovative graph coloring paradigm. Furthermore, we analyze the computational complexity of the problem and prove its NP-completeness for arbitrary graphs. As part of our contributions, we determine the exact values of the geodesic dominated chromatic number for various graph structures, such as cycle, hypermesh, complete binary tree, sibling tree, and hypertree. |
| format | Article |
| id | doaj-art-aa6907ec3e0148b9aa5bc240d9eff82f |
| institution | DOAJ |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-aa6907ec3e0148b9aa5bc240d9eff82f2025-08-20T02:45:31ZengIEEEIEEE Access2169-35362025-01-0113332593327410.1109/ACCESS.2025.354242710890956Geodesic Dominated Coloring of GraphsM. Paruvatha Vathana0https://orcid.org/0009-0005-6080-6828R. Jayagopal1https://orcid.org/0000-0002-7878-1578School of Advanced Sciences, Vellore Institute of Technology, Chennai, IndiaSchool of Advanced Sciences, Vellore Institute of Technology, Chennai, IndiaIn this paper, we introduce geodesic dominated coloring, a novel variant of dominated coloring in graphs, where each color class is dominated by at least one geodesic. This concept builds upon the classical dominated coloring framework, offering fresh perspectives on vertex domination and graph coloring. We begin by examining the intricate relationships between domination parameters closely linked to geodesic dominated coloring, emphasizing their connections, contrasts, and the transfer of hereditary properties. To motivate this study, we highlight the significance of geodesic dominated coloring and its potential applications across diverse domains. We establish key foundational results, including lower bounds for the geodesic dominated chromatic number, to provide deeper insights into this innovative graph coloring paradigm. Furthermore, we analyze the computational complexity of the problem and prove its NP-completeness for arbitrary graphs. As part of our contributions, we determine the exact values of the geodesic dominated chromatic number for various graph structures, such as cycle, hypermesh, complete binary tree, sibling tree, and hypertree.https://ieeexplore.ieee.org/document/10890956/Complete binary treedominated coloringdominating setgeodesic dominated coloringhypermeshhypertree |
| spellingShingle | M. Paruvatha Vathana R. Jayagopal Geodesic Dominated Coloring of Graphs IEEE Access Complete binary tree dominated coloring dominating set geodesic dominated coloring hypermesh hypertree |
| title | Geodesic Dominated Coloring of Graphs |
| title_full | Geodesic Dominated Coloring of Graphs |
| title_fullStr | Geodesic Dominated Coloring of Graphs |
| title_full_unstemmed | Geodesic Dominated Coloring of Graphs |
| title_short | Geodesic Dominated Coloring of Graphs |
| title_sort | geodesic dominated coloring of graphs |
| topic | Complete binary tree dominated coloring dominating set geodesic dominated coloring hypermesh hypertree |
| url | https://ieeexplore.ieee.org/document/10890956/ |
| work_keys_str_mv | AT mparuvathavathana geodesicdominatedcoloringofgraphs AT rjayagopal geodesicdominatedcoloringofgraphs |