Codiameters of 3-connected 3-domination critical graphs (Q2778284)

The codiameter of a graph is a concept dual to the diameter in some sense. For two vertices \(u\) and \(v\) of a graph \(G\) let \(p(u,v)\) be the maximum length of a path connecting \(u\) and \(v\) in \(G\). The codiameter of \(G\) is defined as \(d^*(G)= \min\{p(u,v)\mid u,v\in V(G)\}\). A subset \(S\) of \(V(G)\) is called dominating in \(G\), if each vertex \(v\) of \(G\) either is in \(S\), or is adjacent to a vertex of \(S\). The minimum number of vertices of a dominating set in \(G\) is its domination number \(\gamma(G)\). If \(\gamma(G)= 3\) and the domination number equals two for the graph \(G\) enlarged by any edge from its complement, then \(G\) is called 2-domination critical (or shortly, 3-critical). The main theorem says that for \(G\) being a 3-connected 3-critical graph with \(n\) vertices, \(d^*(G)\geq n-2\).