## DIMACS TR: 93-03

## k-Neighborhood Covering and Independence Problems

### Authors: Shiow-Fen Hwang and Gerard J. Chang

**
ABSTRACT
**

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) <= k and
d(z,y) <= k. A k-neighborhood covering set is a set C of vertices
such that every edge in E is k-neighborhood 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-neighborhood covered by the same vertex in V.
In this paper we first prove that the k-neighborhood covering and the
k-neighborhood independence problems are NP-complete for chordal graphs.
We then present a linear time algorithm for finding a minimum k-neighborhood
covering set and a maximum k-neighborhood independent set of a strongly
chordal graph.
Keywords: k-neighborhood covering, k-neighborhood independence, chordal graph,
strongly chordal graph, strong elimination order.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-03.ps

DIMACS Home Page