2018/10/03 by Rocío M. Casablanca, Lucas Mol, Casablanca, Rocío M. +3
Mathematics · #05C35 #05C40 #05C75 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C35 #msc:05C40 #msc:05C75
paper · pdf · doi:10.48550/arxiv.1810.01972
28 pages, contains minor corrections
arxiv created 2018/10/23 · arxiv updated 2018/10/25
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)=∑_\u,v\⊆ V(G) κG(u,v)/\tbinomn2, and the average edge-connectivity of G is defined by λ(G)=∑_\u,v\⊆ V(G) λG(u,v)/\tbinomn2. A graph G is called ideally connected if κG(u,v)=min\deg(u),deg(v)\ for all 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)<\tfrac94 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)<\tfrac94 for any minimally 2-edge-connected graph G, and provide a similar characterization of the extremal graphs.