Some structures of \(3-({\gamma}_c, 2)\)-critical graphs which are not \(3-{\gamma}_c\)-critical (Q2811688)

The smallest cardinality of a connected dominating set in a graph \(G\) is called the connected domination number of \(G\) and is denoted by \(\gamma_c(G)\). If \(\gamma_c(G)=k\) and \(\gamma_c(G+uv) < k\) for every pair of non-adjacent vertices \(u\) and \(v\) of \(G\), then \(G\) is \(k\)-critical and if \(\gamma_c(G+uv) <k\) for every pair \(u, v\) of nonadjacent vertices with \(d(u,v) \leq t\), then \(G\) is \(k\)-(\(\gamma_c,t\))-critical. Let \(G\) be a \(3\)-(\(\gamma_c,2\))-critical graphs of diameter \(3\) which is not \(3\)-\(\gamma_c\)-critical and suppose \(u\) and \(z\) are vertices of \(G\) distance \(3\) apart such that \(\gamma_c(G+uz)=3\). Let \(V_i\), \(1 \leq i \leq 3\), be the vertices distance \(i\) from \(u\) in \(G\). The authors give characterizations of such graphs \(G\) when \(V_1\) is an independent set and the case where both \(V_1\) and \(V_2\) induce complete graphs.