The maximum average connectivity among all orientations of a graph

• Published in: arXiv.org 2019-07
• Main Authors: Casablanca, Rocio M, Dankelmann, Peter, Goddard, Wayne, Oellermann, Ortrud R, Mol, Lucas
• Format: Article
• Language: English
• Subjects: Apexes; Connectivity; Graph theory; Graphs; Sharpness; Trees (mathematics)
• ISSN: 2331-8422

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.