Average connectivity of minimally 2-connected graphs and average edge-connectivity of minimally 2-edge-connected graphs

Abstract

Let $G$ be a (multi)graph of order $n$ and let $u,v$ be vertices of $G$. The maximum number of internally disjoint $u$-$v$ paths in $G$ is denoted by ${\kappa }_G(u,v)$, and the maximum number of edge-disjoint $u$-$v$ paths in $G$ is denoted by ${\lambda }_G(u,v)$. The average connectivity of $G$ is defined by $\overline{\kappa }(G)={\sum }_{\{u,v\}\subseteq V(G)}{\kappa }_G(u,v)/\left(\genfrac{}{}{0ex}{}{n}{2}\right),$ and the average edge-connectivity of $G$ is defined by $\overline{\lambda }(G)={\sum }_{\{u,v\}\subseteq V(G)}{\lambda }_G(u,v)/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. A graph $G$ is called ideally connected if ${\kappa }_G(u,v)=\min \{\mathrm{deg}(u),\mathrm{deg}(v)\}$ for all pairs of vertices $\{u,v\}$ of $G$. We prove that every minimally $2$-connected graph of order $n$ with largest average connectivity is bipartite, with the set of vertices of degree $2$ and the set of vertices of degree at least $3$ being the partite sets. We use this structure to prove that $\overline{\kappa }(G)<\frac{9}{4}$ for any minimally $2$-connected graph $G$. This bound is asymptotically tight, and we prove that every extremal graph of order $n$ is obtained from some ideally connected nearly regular graph on roughly $n/4$ vertices and $3n/4$ edges by subdividing every edge. We also prove that $\overline{\lambda }(G)<\frac{9}{4}$ for any minimally $2$-edge-connected graph $G$, and provide a similar characterization of the extremal graphs.

28 pages, contains minor corrections