Structural Bounds and Algorithms for Dominator and Distance-k Dominator Coloring in Product Graphs

Abstract

Dominator coloring combines vertex coloring and domination by requiring that each color class contain a dominating vertex. In this paper, we investigate dominator and distance-$k$ dominator coloring in product graphs. Sharp upper and lower bounds are established for Cartesian, strong, and brick products.
We further analyze the computational complexity of the associated decision problems and propose efficient greedy algorithms supported by integer linear programming formulations. The obtained results unify and extend several known bounds and provide scalable algorithmic insights for large structured networks.