In this contribution, we study the total { k }-domination number on graphs. We establish a general upper bound for this number and provide sufficient conditions on a graph to satisfy it at equality. Moreover, for the family of caterpillar graphs, this bound is also tight. The total { k }-domination problem consists of finding a function of minimum value, defined on a set of vertices in a graph, such that in any open neighborhood it has value at least k. We focus on this problem in caterpillar graphs and show that, on this family, it can be reduced to the usual total domination problem (k = 1). Then, we present a representation of a caterpillar in terms of the number of vertices of degree 3 (parents) in it, and the length of the paths induced between two consecutive parents in the central path of the caterpillar. Using this representation, we establish the main result of this work: the value of the total { k }-domination number of every caterpillar, for all k .

A new framework for conflict-free coloring of hypergraphs is presented, leading to a novel graph problem which generalizes the partition and the list coloring problems, well-known for their multiple applications. Two integer linear programming formulations are proposed for this problem: a compact formulation inspired by the pioneering formulation for the vertex coloring problem and a set covering formulation whose variables are associated with stable sets. For the latter formulation, a branch-and-price algorithm is developed. Computational experiments in random instances validate the superiority of this approach over the direct solution of the compact formulation with a commercial solver.

ABSTRACT In the minimum clique routing problem on cycles mcrpc, we are given a cycle together with a set of demands (weighted terminals pairs) and the goal is to route all the pairs minimizing the maximum weight clique of the intersection graph induced by the routing. The nodes of this graph are the demands with their corresponding weights and two demands are adjacent when their routes share at least one arc. In this work, we are not only interested in the mcrpc but also in two natural subproblems. First, we consider the situation where the demands are disjoint, in the sense that every two demands do not share any of their corresponding terminals. Second, we analyze the subproblem where the weights of the routes are all equal. We first show that the problem is NP‐hard even in the subproblem of disjoint demands. For the case of arbitrary weights, we exhibit a simple combinatorial 2‐approximation algorithm and a ‐approximation algorithm based on rounding a solution of a relaxation of an integer linear programming formulation of our problem. Finally, we give a fixed parameter tractable algorithm for the case of uniform weights, whose parameter is the maximum number of demands for which a demand exists whose terminals alternate in the cycle with the terminals of each of them.