On maximum critically h-connected graphs (Q801933)

Fix the integer \(h\geq 2\). An h-connected graph G is said to be critically h-connected in G-v has connectivity h-1 for \(v\in V(G)\). Denote by \({\mathcal C}\) the set of all critically h-connected graphs and by \({\mathcal A}\) the subset of \({\mathcal C}\) of those graphs in which each vertex is adjacent to a vertex with degree h. Let \(\hat {\mathcal C}\) and \(\hat {\mathcal A}\) be the subsets of \({\mathcal C}\) and \({\mathcal A}\), respectively, containing those graphs which, for given order, have the maximum number of edges. The authors determine \(\hat {\mathcal A}\) for \(h\geq 2\). It follows from the reviewer's characterization of \(\hat {\mathcal C}\) for \(h=2\) that \(\hat {\mathcal A}\neq \hat {\mathcal C}\) in this case. In contrast, the authors show that \(\hat {\mathcal A}=\hat {\mathcal C}\) for \(h=3\) and conjecture that this is so for \(h>3\) also.