## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 543-570 |

Number of pages | 28 |

Journal | Journal of Combinatorial Optimization |

Volume | 43 |

Issue number | 3 |

DOIs | |

Publication status | Published - Apr 2022 |

## Keywords

- Average connectivity
- Connectivity
- Cubic graphs
- Maximal outerplanar graphs
- Minimally 2-connected graphs
- Orientations

## ASJC Scopus subject areas

- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics