×

Algorithmic aspects of neighborhood numbers. (English) Zbl 0777.05085

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.

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
PDFBibTeX XMLCite
Full Text: DOI Link