On perfect neighborhood sets in graphs (Q1297450)

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)\).