The maximum average connectivity among all orientations of a graph

• Published in: Journal of combinatorial optimization 2022-04, Vol.43 (3), p.543-570
• Main Authors: Casablanca, Rocío M., Dankelmann, Peter, Goddard, Wayne, Mol, Lucas, Oellermann, Ortrud
• Format: Article
• Language: English
• Subjects: Apexes; Combinatorics; Connectivity; Convex and Discrete Geometry; Graph theory; Graphs; Mathematical Modeling and Industrial Mathematics; Mathematics; Mathematics and Statistics; Operations Research/Decision Theory; Optimization; Theory of Computation; Trees (mathematics)
• ISSN: 1382-6905; 1573-2886
• DOI: 10.1007/s10878-021-00789-z

For distinct vertices u and v in a graph G , the connectivity between u and v , denoted κ G ( u , v ) , is the maximum number of internally disjoint u – v paths in G . The average connectivity of G , denoted κ ¯ ( G ) , is the average of κ 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 κ D ( u , v ) , is the maximum number of internally disjoint directed u – v paths in D . The average connectivity of D , denoted κ ¯ ( D ) , is the average of κ 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 κ ¯ max ( G ) denote the maximum average connectivity among all orientations of G . In this paper we obtain bounds for κ ¯ max ( G ) and for the ratio κ ¯ 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.