Average connectivity of minimally 2-connected graphs and average edge-connectivity of minimally 2-edge-connected graphs

Abstract

Let G be a (multi)graph of order n and let u, v be vertices of G. The maximum number of internally disjoint u–v paths in G is denoted by κG(u, v), and the maximum number of edge-disjoint u–v paths in G is denoted by λG(u, v). The average connectivity of G is defined by κ(G) = Σ κG(u, v)/ (n2 ) , and the average edge-connectivity of G is defined by λ(G) = Σ λG(u, v)/ (n2 ) , where both sums run over all unordered pairs of vertices {u, v} ⊆ V(G). A graph G is called ideally connected if κG(u, v) = min{deg(u), deg(v)} for all unordered pairs of vertices {u, v} of G. We prove that every minimally 2-connected graph of order n with largest average connectivity is bipartite, with the set of vertices of degree 2 and the set of vertices of degree at least 3 being the partite sets. We use this structure to prove that κ(G) < 9 4 for any minimally 2-connected graph G. This bound is asymptotically tight, and we prove that every extremal graph of order n is obtained from some ideally connected nearly regular graph on roughly n/4 vertices and 3n/4 edges by subdividing every edge. We also prove that λ(G) < 9 4 for any minimally 2-edge-connected graph G, and provide a similar characterization of the extremal graphs.