ALGORITHMIC ASPECTS OF NEIGHBORHOOD NUMBERS

Abstract

In a graph G = (V, E), E[v] denotes the set of edges in the subgraph induced by N[v] = {v} or {u is-an-element-of V: uv is-an-element-of E}. The neighborhood-covering problem is to find the minimum cardinality of a set C of vertices such that E = or {E[v]: v is-an-element-of C}. The neighborhood-independence problem is to find the maximum cardinality of a set of edges in which there are no two distinct edges belonging to the same E[v] for any v is-an-element-of V. Two other related problems are the clique-transversal problem and the clique-independence problem. It is shown that these four problems are NP-complete in split graphs with degree constraints and linear time algorithms for them are given in a strongly chordal graph when a strong elimination order is given.