Characterizations of minimal graphs with equal edge connectivity and spanning tree packing number

Abstract

With graphs considered as natural models for many network design problems, edge connectivity ${\kappa }^{\prime }(G)$ and maximum number of edge-disjoint spanning trees $\tau (G)$ of a graph $G$ have been used as measures for reliability and strength in communication networks modeled as graph $G$ (see \cite{Cunn85, Matula87}, among others). Mader \cite{Mader71} and Matula \cite{Matula72} introduced the maximum subgraph edge connectivity $\overline{κ'}(G)=\max \{κ'(H): H \mbox{ is a subgraph of } G \}$. Motivated by their applications in network design and by the established inequalities \[ \overline{κ'}(G)\ge κ'(G) \ge τ(G), \] we present the following in this paper: (i) For each integer $k>0$, a characterization for graphs $G$ with the property that $\overline{{\kappa }^{\prime }}(G)\le k$ but for any edge $e$ not in $G$, $\overline{{\kappa }^{\prime }}(G+e)\ge k+1$. (ii) For any integer $n>0$, a characterization for graphs $G$ with $|V(G)|=n$ such that ${\kappa }^{\prime }(G)=\tau (G)$ with $|E(G)|$ minimized.

The manuscript was published with a different title "Characterizations of strength extremal graphs" in Graphs and Combinatorics. As it was cited by several publications with previous title, we make an announcement here