Geodesic Dominated Coloring of Graphs
M. Paruvatha vathana, R. Jayagopal · IEEE Access · 2025
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.