2025/02/11 by María A. Garrido-Vizuete, Mucuy-kak Guevara, Garrido-Vizuete, María A. +5
Computer Science · Engineering · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2502.07248
This paper introduces the concept of domination in the context of colored graphs (where each color assigns a weight to the vertices of its class), termed up-color domination, where a vertex dominating another must be heavier than the other. That idea defines, on one hand, a new parameter measuring the size of minimal dominating sets satisfying specific constraints related to vertex colors. The paper proves that the optimization problem associated with that concept is an NP-complete problem, even for bipartite graphs with three colors. On the other hand, a weight-based variant, the up-color domination weight, is proposed, further establishing its computational hardness. The work also explores the relationship between up-color domination and classical domination and coloring concepts. Efficient algorithms for trees are developed that use their acyclic structure to achieve polynomial-time solutions.