Minimum r-neighborhood covering set of permutation graphs

Abstract

For a connected graph G(V,E) and a fixed integer r > 0, a node q ∈ V r-dominates another node s ∈ V if d(q, s) ≤ r. An edge (q, s) is r-neighborhood covered by a vertex t, if d(q, t) ≤ r and d(s, t) ≤ r, i.e., both the vertices q and s are r-dominated by the vertex t. A set Cr ⊆ V is known to be a r-neighborhood covering (r-NC) set of graph G if and only if one or more vertices of Cr r-dominate each edge in E. Among all r-NC sets of graph G, the set with fewest cardinality is the minimum r-NC set of G and we indicate its cardinality as r-NC-number and we denote it by the symbol ρ(G, r). This is an NPcomplete problem on general graphs. It is also NP-complete for chordal graphs. Here, we develop an O(n) time algorithm for computing a minimum r-NC set of permutation graphs, where n indicates the order of the set V .