K-NEIGHBORHOOD-COVERING AND K-NEIGHBORHOOD-INDEPENDENCE PROBLEMS FOR CHORDAL GRAPHS

Suppose G = (V, E) is a simple graph and k is a fixed positive integer . A vertex z k-neighborhood-covers an edge (x, y) if d(z, x) less than or equal to k and d(z, y) less than or equal to k. A k-neighborhood-c overing set is a set C of vertices such that every edge in E is k-neig hborhood-covered by some vertex in C. A k-neighborhood-independent set is a set of edges in which no two distinct edges can be k-neighborhoo d-covered by the same vertex in V. In this paper we first prove that t he neighborhood-covering and the k-neighborhood-independence problems are NP-complete for chordal graphs. We then present a linear-time algo rithm for finding a minimum k-neighborhood-covering set and a maximum k-neighborhood-independent set for a strongly chordal graph provided t hat a strong elimination ordering is given in advance.