For distinct vertices $u$ and $v$ in a graph $G$, the { \em connectivity} between $u$ and $v$, denoted $\kappa_G(u,v)$, is the maximum number of internally disjoint $u$--$v$ paths in $G$. The { \em average connectivity} of $G$, denoted $\overline{ \kappa}(G),$ is the average of $\kappa_G(u,v)$ taken over all unordered pairs of distinct vertices $u,v$ of $G$. Analogously, for a directed graph $D$, the { \em connectivity} from $u$ to $v$, denoted $\kappa_D(u,v)$, is the maximum number of internally disjoint directed $u$--$v$ paths in $D$. The { \em average connectivity} of $D$, denoted $\overline{ \kappa}(D)$, is the average of $\kappa_D(u,v)$ taken over all ordered pairs of distinct vertices $u,v$ of $D$. An { \em orientation} of a graph $G$ is a directed graph obtained by assigning a direction to every edge of $G$. For a graph $G$, let $\overline{ \kappa}_{ \max}(G)$ denote the maximum average connectivity among all orientations of $G$. In this paper we obtain bounds for $\overline{ \kappa}_{ \max}(G)$ and for the ratio $\overline{ \kappa}_{ \max}(G)/\overline{ \kappa}(G)$ for all graphs $G$ of a given order and in a given class of graphs. Whenever possible, we demonstrate sharpness of these bounds. This problem had previously been studied for trees. We focus on the classes of cubic $3$-connected graphs, minimally $2$-connected graphs, $2$-trees, and maximal outerplanar graphs.
Categories: math.CO