The maximum average connectivity among all orientations of a graph

For distinct vertices u and v in a graph G, the connectivity between u and v, denoted $$\kappa _G(u,v)$$ κ G ( u , v ) , is the maximum number of internally disjoint u–v paths in G. The average connectivity of G, denoted $${\overline{\kappa }}(G),$$ κ ¯ ( G ) , is the average of $$\kappa _G(u,v)$$ κ G ( u , v ) taken over all unordered pairs of distinct vertices u, v of G. Analogously, for a directed graph D, the connectivity from u to v, denoted $$\kappa _D(u,v)$$ κ D ( u , v ) , is the maximum number of internally disjoint directed u–v paths in D. The average connectivity of D, denoted $${\overline{\kappa }}(D)$$ κ ¯ ( D ) , is the average of $$\kappa _D(u,v)$$ κ D ( u , v ) taken over all ordered pairs of distinct vertices u, v of D. An 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)$$ κ ¯ max ( G ) denote the maximum average connectivity among all orientations of G. In this paper we obtain bounds for $${\overline{\kappa }}_{\max }(G)$$ κ ¯ max ( G ) and for the ratio $${\overline{\kappa }}_{\max }(G)/{\overline{\kappa }}(G)$$ κ ¯ max ( G ) / κ ¯ ( 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.