The codiameter of a 2-connected graph (Q2463471): Difference between revisions

Let \(G\) be a finite undirected simple graph. The codiameter \(d^*(G)\) of a graph \(G\) is defined as the minimum, taken over all pairs of vertices \(u\) and \(v\) in \(G\), of the maximum length of a \(uv\)-path. It is easy to see that this notion is of interest only if the graph is at least \(2\)-connected. For \(2\)-connected graphs \textit{G. Fan} [J. Comb. Theory, Ser. B 49, No. 2, 151--180 (1990; Zbl 0713.05043)] proved that a codiameter of \(G\) is at least \(c\) if \(c\geq 3\) \((c\in {\mathbb{ N}})\), \(G\) has \(n\) vertices and more than \(\alpha:=\frac{(c+1)(n-2)}2+1\) edges. This result is the best possible when \(n-2\) is divisible by \(c-2\). The main purpose of the paper is to show that the bound \(\alpha\) can be decreased when \(n-2\) is not divisible by \(c-2\). The authors prove several auxiliary lemmas of independent interest.