On the Average (Edge-)Connectivity of Minimally k-(Edge-)Connected Graphs
share
Let G be a graph of order n and let u,v be vertices of G. Let κ_G(u,v) denote the maximum number of internally disjoint u-v paths in G. Then the average connectivity κ(G) of G, is defined as κ(G)=∑_{u,v}⊆ V(G)κ_G(u,v)/n2. If k ≥ 1 is an integer, then G is minimally k-connected if κ(G)=k and κ(G-e) < k for every edge e of G. We say that G is an optimal minimally k-connected graph if G has maximum average connectivity among all minimally k-connected graphs of order n. Based on a recent structure result for minimally 2-connected graphs we conjecture that, for every integer k ≥3, if G is an optimal minimally k-connected graph of order n≥ 2k+1, then G is bipartite, with the set of vertices of degree k and the set of vertices of degree exceeding k as its partite sets. We show that if this conjecture is true, then κ(G)< 9k/8 for every minimally k-connected graph G. For every k ≥ 3, we describe an infinite family of minimally k-connected graphs whose average connectivity is asymptotically 9k/8. Analogous results are established for the average edge-connectivity of minimally k-edge-connected graphs.
READ FULL TEXT