Vertex criticality for upper domination and irredundance (Q2746202)

A subset \(S\) of the vertex set \(V(G)\) 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\). A set \(S\subseteq V(G)\) is called irredundant, if each vertex \(v\in S\) has a private neighbour in \(S\), i.e. a vertex adjacent to \(x\) and to no other vertex of \(S\). The maximum number of vertices of a dominating (or irredundant) set minimal with respect to set inclusion in \(G\) is the upper domination number \(\Gamma(G)\) (or upper irredundance number \(\text{IR}(G)\)) of \(G\). Let \(G-x\) be the graph obtained by removing the vertex \(x\) from the graph \(G\). If \(\Gamma(G- x)< \Gamma(G)\) (or \(\text{IR}(G- x)< \text{IR}(G)\)) for each vertex \(x\) of \(G\), then \(G\) is called \(\Gamma\)-critical (or \(\text{IR}\)-critical respectively). If \(\Gamma(G- x)> \Gamma(G)\) for each vertex \(x\) of \(G\), then \(G\) is called \(\Gamma^+\)-critical. The paper states that a graph is \(\text{IR}\)-critical if and only if it is \(\Gamma\)-critical and characterizes the class of all \(\Gamma^+\)-critical graphs.