On extremal graphs with at most $\ell$ internally disjoint Steiner trees connecting any n-1 vertices

Abstract

The concept of maximum local connectivity $\bar{\hat{I}}º$ of a graph was introduced by Bollobás. One of the problems about it is to determine the largest number of edges $f(n;\bar{\hat{I}}º\le \ell )$ for graphs of order $n$ that have local connectivity at most $\ell$. We consider a generalization of the above concept and problem. For $S\subseteq V(G)$ and $|S|\ge 2$, the \emph{generalized local connectivity} $\hat{I}º(S)$ is the maximum number of internally disjoint trees connecting $S$ in $G$. The parameter $\bar{\hat{I}}{º}_k(G)=max\{\hat{I}º(S)|S\subseteq V(G),|S|=k\}$ is called the \emph{maximum generalized local connectivity} of $G$. This paper it to consider the problem of determining the largest number $f(n;\bar{\hat{I}}{º}_k\le \ell )$ of edges for graphs of order $n$ that have maximum generalized local connectivity at most $\ell$. The exact value of $f(n;\bar{\hat{I}}{º}_k\le \ell )$ for $k=n,n-1$ is determined. For a general $k$, we construct a graph to obtain a sharp lower bound.

19 pages