Minimum ağırlıklı mükemmel komşuluk kümesi problemi

Given an undirected simple graph G = (V,E), the open neighborhood of a vertex j ∈ V, denoted by δ(j), is defined as the set of all vertices that are adjacent to j , i.e., δ(j) = {i|{i,j} ∈ E}. The closed neighborhood of a vertex j, denoted by Δ(j), is defined as Δ(j) = δ(j)∪{j}. For a set S ⊆ V, a vertex j is said to be perfect with respect to S, i.e., S-perfect, if |Δ(j)∩S|=1. The set S is said to be a perfect neighborhood set if the set of S-perfect vertices dominate G. Hedetniemi et al. (1997) proposed a linear-time algorithm for the minimum cardinality perfect neighborhood set problem when G is a tree. We observe some flaws in the proposed algorithm and correct them. Moreover, we consider the weighted version of the problem, where the weight of a perfect neighborhood set S is defined as ∑j∈V (wjyj + vjxj). Here yj and xj are binary parameters taking the value 1 if and only if j is in S and j is S-perfect, respectively, and wj and vj are the weights associated with vertex j. We extend the algorithm proposed by Hedetniemi et al. for trees to the weighted case and check its correctness by comparing its solutions with the solutions of an integer programming formulation that we propose for arbitrary graphs. Additionally, we provide some valid inequalities for the integer programming formulation to make it stronger, and characterize the perfect neighborhood set polytope for star graphs and complete graphs by the help of these valid inequalities. Finally, we conduct computational experiments to see the effects of these valid inequalities.