pith. sign in

arxiv: 1301.4623 · v1 · pith:7JKSGXNJnew · submitted 2013-01-20 · 🧮 math.CO

On extremal graphs with exactly one Steiner tree connecting any k vertices

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

The problem of determining the largest number $f(n;\bar{\kappa}\leq \ell)$ of edges for graphs with $n$ vertices and maximal local connectivity at most $\ell$ was considered by Bollob\'{a}s. Li et al. studied the largest number $f(n;\bar{\kappa}_3\leq2)$ of edges for graphs with $n$ vertices and at most two internally disjoint Steiner trees connecting any three vertices. In this paper, we further study the largest number $f(n;\bar{\kappa}_k=1)$ of edges for graphs with $n$ vertices and exactly one Steiner tree connecting any $k$ vertices with $k\geq 3$. It turns out that this is not an easy task to finish, not like the same problem for the classical connectivity parameter. We determine the exact values of $f(n;\bar{\kappa}_k=1)$ for $k=3,4,n$, respectively, and characterize the graphs which attain each of these values.

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.