Chang, Gerard J.; Farber, Martin; Tuza, Zsolt Algorithmic aspects of neighborhood numbers. (English) Zbl 0777.05085 SIAM J. Discrete Math. 6, No. 1, 24-29 (1993). In a graph \(G=(V,E)\) let \(E[v]\) denote the edge set of the subgraph induced by \(N[v]=\{v\}\cup\{u\in V;uv\in E\}\). The neighbourhood covering problem is to find the minimum cardinality of a set \(C\) of vertices such that \(E=\bigcup\{E[v];v\in C\}\). The neighbourhood independence problem is to find the maximum cardinality of a set of edges in which there are not two distinct edges that belong 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 all the four are NP- complete in split graphs with linear degree constraints. In contrast, the problems are linear in strongly chordal graphs when a strong elimination order is given. Reviewer: Št.Znám (Bratislava) Cited in 1 ReviewCited in 31 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C85 Graph algorithms (graph-theoretic aspects) 05C35 Extremal problems in graph theory 68R10 Graph theory (including graph drawing) in computer science Keywords:neighbourhood covering problem; neighbourhood independence problem; clique-transversal problem; clique-independence problem; NP-complete; chordal graphs PDFBibTeX XMLCite \textit{G. J. Chang} et al., SIAM J. Discrete Math. 6, No. 1, 24--29 (1993; Zbl 0777.05085) Full Text: DOI Link