Algorithmic Aspects of Neighborhood Numbers
Gerard J. Chang, Martin Farber, Zs. Tuza · SIAM Journal on Discrete Mathematics · 1993
In a graph $G = ( V,E ),E [ v ]$ denotes the set of edges in the subgraph induced by $N [ v ] \equiv \{ v \} \cup \{ u \in V:uv \in E \}$. The neighborhood-covering problem is to find the minimum cardinality of a set C of vertices such that $E = \cup \{ E [ v ]:v \in 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 \in 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.