2019/07/16 by Rocio M. Casablanca, Peter Dankelmann, Casablanca, Rocio M. +7
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1907.07219
28 pages
arxiv created 2019/07/16 · arxiv updated 2019/07/18
For distinct vertices u and v in a graph G, the \em connectivity between u and v, denoted κG(u,v), is the maximum number of internally disjoint u--v paths in G. The \em 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 \em connectivity from u to v, denoted κD(u,v), is the maximum number of internally disjoint directed u--v paths in D. The \em 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 \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 κ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.