The maximum average connectivity among all orientations of a graph (Q2125229)

This paper studies the maximum average connectivity among all orientations of a graph. The average connectivity of a directed graph \(D\) is denoted by \(\bar{k}(D)\), which is the average of the connectivity between two vertices over all such possible pairs in \(D\). The maximum average connectivity among all orientations of a given graph \(G\) is denoted by \(\bar{k}_{\max}(G)\). If a graph \(G\) is \(r\)-regular over \(n\) vertices for some odd \(r\), it is shown that \(\bar{k}_{\max}(G)\le\frac{r-1}{2}+\frac{n}{4(n-1)}\). If \(G\) is minimally 2-connected over \(n\) vertices, then \(1\le \bar{k}_{\max}(G)<5/4\). For each minimally 2-connected graph \(G\), it is shown that \(4/9<\bar{k}_{\max}(G)/\bar{k}(G)<5/8\). When \(G\) is a maximal outerplanar graph, it is shown that \(\bar{k}_{\max}(G)\le 3/2+(n-5)/(n^2-n)\).