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

Casablanca, Rocío M. Mol L. Oellermann O.R.
Discrete Applied Mathematics
Doi 10.1016/j.dam.2020.10.015
Volumen 289 páginas 233 - 247
2021-01-31
Citas: 5
Abstract
© 2020 Elsevier B.V.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 [Formula presented], and the average edge-connectivity of G is defined by [Formula presented], 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 [Formula presented] 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 [Formula presented] for any minimally 2-edge-connected graph G, and provide a similar characterization of the extremal graphs.
Maximum average connectivity, Maximum average edge-connectivity, Minimally 2-connected, Minimally 2-edge-connected
Datos de publicaciones obtenidos de Scopus