On perfect neighborhood sets in graphs
Two numerical invariants of graphs, namely the upper domination number \(\Gamma(G)\) and the upper perfect neighbourhood number \(\Theta(G)\), are considered and their equality is proved. A subset \(S\) of the vertex set \(V\) of a graph \(G\) is called dominating in \(G\), if each vertex of \(G\) either is in \(S\), or is adjacent to a vertex of \(S\). The maximum number of vertices of a minimal (with respect to set inclusion) dominating set in \(G\) is the upper domination number \(\Gamma(G)\) of \(G\). A vertex \(v\) of \(G\) is said to be \(S\)-perfect, if its closed neighbourhood \(N[v]\) has exactly one vertex in common with \(S\). If every vertex of \(G\) is \(S\)-perfect or adjacent to an \(S\)-perfect vertex, then the set \(S\) is called a perfect neighbourhood set. The maximum number of vertices of a perfect neighbourhood set in \(G\) is the upper perfect neighbourhood number \(\Theta(G)\) of \(G\). The main result of the paper states that \(\Theta(G)= \Gamma(G)\).
scientific article; zbMATH DE number 1321806