On the Average (Edge-)Connectivity of Minimally $k$-(Edge-)Connected Graphs

Let $G$ be a graph of order $n$ and let $u,v$ be vertices of $G$. Let $\kappa_G(u,v)$ denote the maximum number of internally disjoint $u$--$v$ paths in $G$. Then the average connectivity $\overline{\kappa}(G)$ of $G$, is defined as $ \overline{\kappa}(G)=\sum_{\{u,v\}\subseteq V(G)} \kappa_G(u,v)/\tbinom{n}{2}. $ If $k \ge 1$ is an integer, then $G$ is minimally $k$-connected if $\kappa(G)=k$ and $\kappa(G-e) < k$ for every edge $e$ of $G$. We say that $G$ is an optimal minimally $k$-connected graph if $G$ has maximum average connectivity among all minimally $k$-connected graphs of order $n$. Casablanca, Mol and Oellermann showed that every optimal minimally 2-connected graph $G$ is bipartite, with the set of vertices of degree 2 and the set of vertices of degree exceeding 2 forming the partite sets. They also proved that $\overline{\kappa}(G) < 9/4$ for all minimally $2$-connected graphs $G$ and that this bound is asymptotically sharp. We conjecture that for every integer $k \ge 3$, if $G$ is an optimal minimally $k$-connected graph of order $n\geq 2k+1$, then $G$ is bipartite, with the set of vertices of degree $k$ and the set of vertices of degree exceeding $k$ as its partite sets. We show that if this conjecture is true, then $\overline{\kappa}(G)< 9k/8$ for every minimally $k$-connected graph $G$. For every $k \ge 3$, we describe an infinite family of minimally $k$-connected graphs whose average connectivity is asymptotically $9k/8$. Analogous results are established for the average edge-connectivity of minimally $k$-edge-connected graphs.