pith. sign in

arxiv: 1304.3774 · v1 · pith:67G2YZ5Onew · submitted 2013-04-13 · 🧮 math.CO

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

classification 🧮 math.CO
keywords kappaconnectivitylocalmaximumgeneralizedgraphsnumberconcept
0
0 comments X
read the original abstract

The concept of maximum local connectivity $\bar {\kappa}$ of a graph was introduced by Bollob\'{a}s. One of the problems about it is to determine the largest number of edges $f(n;\bar{\kappa}\leq \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|\geq 2$, the \emph{generalized local connectivity} $\kappa(S)$ is the maximum number of internally disjoint trees connecting $S$ in $G$. The parameter $\bar{\kappa}_k(G)=max\{\kappa(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{\kappa}_k\leq \ell)$ of edges for graphs of order $n$ that have maximum generalized local connectivity at most $\ell$. The exact value of $f(n;\bar{\kappa}_k\leq \ell)$ for $k=n,n-1$ is determined. For a general $k$, we construct a graph to obtain a sharp lower bound.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.