The maximum average connectivity among all orientations of a graph

Casablanca, Rocío M. Dankelmann P. Goddard W. Mol L. Oellermann O.R.
Journal of Combinatorial Optimization
Doi 10.1007/s10878-021-00789-z
2021-01-01
Citas: 3
Abstract
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.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.
Average connectivity, Connectivity, Cubic graphs, Maximal outerplanar graphs, Minimally 2-connected graphs, Orientations
Datos de publicaciones obtenidos de Scopus