A polytope P ⊆ [ 0 , 1 ] n is said to have the persistency property if for every vector c ∈ R n and every c -optimal point x ∈ P , there exists a c -optimal integer point y ∈ P ∩ { 0 , 1 } n such that x i = y i for each i ∈ { 1 , … , n } with x i ∈ { 0 , 1 } . In this paper, we consider a relaxation of the persistency property called 1-persistency . We study the family Q of graphs whose clique relaxation of the stable set polytope has 1-persistency, and we refer to them as Q - persistent graphs. We provide sufficient conditions for a graph to be Q -persistent, and identify several graph classes of this family. Motivated by a necessary condition of this property, we introduce the family of ( k , U ) -umbrella graphs, and study which of them belong to Q . The property of being Q -persistent is a hereditary property for graphs, and then it becomes relevant to study the minimal forbidden structures for the family Q , i.e., minimally not Q -persistent (mn Q ) graphs. In this line, we identify some mn Q ( k , U ) -umbrella graphs and also other forbidden minimal structures for Q -persistency outside this family (named as whale graphs).

Given a set P of paths over a graph, its edge intersection graph is a graph each of whose vertices corresponds to a path in P and where two vertices are connected if and only if the paths they correspond to share at least one edge. EPT is the class of edge intersection graphs of paths over trees. The complete characterization of EPT graphs by minimal forbidden subgraphs is not yet known. In this paper, we introduce two stretching operations on graphs and show that they preserve the property of being non-EPT graphs. We further investigate how to use these operations to construct minimal non- EPT graphs, allowing us to present one of the main results of this contribution, that is, two new infinite families of minimal non-EPT graphs that have not yet been described in the literature.

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 .

The power dominating set problem (PDS) is a graph optimization problem with applications related to the control and monitoring of electric power systems using devices called phasor measurement units (PMUs). The objective of PDS is to find a minimum set of vertices on which to install PMUs that allow monitoring all remaining vertices by recursively applying two observation rules. In particular, the domination rule assumes that a vertex with a PMU can monitor all its neighbors. In real-world applications, PMUs have a predefined number of channels that limit the number of neighbors that they can monitor. This work proposes a novel integer linear programming formulation for the PDS variant that considers PMUs with channel limitation. The formulation is based on a set of constraints to forbid circular precedences that might arise in the application of the observation rules. As the number of constraints grows exponentially, an algorithm is developed to handle them dynamically (as lazy constraints) with an efficient separation routine. Computational experiments are performed on benchmark instances with up to 13.659 vertices to compare the performance of the new formulation with others adapted from the PDS literature. An interesting behavior is observed, where the best-performing formulation strongly depends on the number of limited channels. In particular, the new formulation is effective in instances with moderate channel limitation.

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.

The main purpose of this work is to characterize the graphs whose closed neighbourhood matrices are perfect since this property implies the resolution of some packing problems in polynomial time. Given a 0-1 matrix M, Q(M) denotes the graph whose cliques have their incidence vectors as the rows of M. A 0-1 matrix M is perfect if it is the clique-node matrix of Q(M) and Q(M) is a perfect graph. First, we define a set T of seven graphs and prove that N[G] is a clique-node matrix if and only if every node induced subgraph of G in the set T, has a common neighbour in G. Second, we define two families of graphs, called H-graphs and A-graphs, and prove that Q(N[G]) does not have an induced odd hole if and only if G has no H-subgraph for some additional conditions on G. Finally, we show that Q(N[G]) does not have an induced odd antihole if and only if G has neither an A-subgraph nor a web graph Wt4t+3 in suitable sets of nodes of V(G), thus completing a characterization of graphs with perfect closed neighbourhood matrix.