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

Abstract

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)/\left(\genfrac{}{}{0ex}{}{n}{2}\right).$ 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$. Based on a recent structure result for minimally 2-connected graphs we conjecture that, for every integer $k\ge 3$, if $G$ is an optimal minimally $k$-connected graph of order $n\ge 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.

16 pages, 3 figures. This version includes revisions based on referee comments