The minimal size of a graph with given generalized 3-edge-connectivity

Abstract

For $S\subseteq V(G)$ and $|S|\ge 2$, $\hat{I}»(S)$ is the maximum number of edge-disjoint trees connecting $S$ in $G$. For an integer $k$ with $2\le k\le n$, the \emph{generalized $k$-edge-connectivity} $\hat{I}{»}_k(G)$ of $G$ is then defined as $\hat{I}{»}_k(G)=min\{\hat{I}»(S):S\subseteq V(G)and|S|=k\}$. It is also clear that when $|S|=2$, $\hat{I}{»}_2(G)$ is nothing new but the standard edge-connectivity $\hat{I}»(G)$ of $G$. In this paper, graphs of order $n$ such that $\hat{I}{»}_3(G)=n-3$ is characterized. Furthermore, we determine the minimal number of edges of a graph of order $n$ with $\hat{I}{»}_3=1,n-3,n-2$ and give a sharp lower bound for $2\le \hat{I}{»}_3\le n-4$.

10 pages