ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Z. Jin, B. Sheng, Y. Sun


The minimum size of a graph with given tree connectivity


Discussiones Mathematicae Graph Theory

Received: 2017-10-16, Revised: 2018-11-28, Accepted: 2018-11-28,


For a graph $G=(V,E)$ and a set $S\subseteq V$ of at least two vertices, an $S$-tree is a such subgraph $T$ of $G$ that is a tree with $S\subseteq V(T)$. Two $S$-trees $T_1$ and $T_2$ are said to be internally disjoint if $E(T_1)\cap E(T_2)=\emptyset$ and $V(T_1)\cap V(T_2)=S$, and edge-disjoint if $E(T_1)\cap E(T_2)=\emptyset$. The generalized local connectivity $\kappa_G(S)$ (generalized local edge-connectivity $\lambda_G(S)$, respectively) is the maximum number of internally disjoint (edge-disjoint, respectively) $S$-trees in $G$. For an integer $k$ with $2\leq k\leq n$, the generalized $k$-connectivity (generalized $k$-edge-connectivity, respectively) is defined as $\kappa_k(G)=\min\{\kappa_G(S)| S\subseteq V(G), |S|=k\}$ ($\lambda_k(G)=\min\{\lambda_G(S)| S\subseteq V(G), |S|=k\}$, respectively). Let $f(n,k,t)$ ($g(n,k,t)$, respectively) be the minimum size of a connected graph $G$ with order $n$ and $\kappa_k(G)=t$ ($\lambda_k(G)=t$, respectively), where $3\leq k\leq n$ and $1\leq t\leq n-\left \lceil\frac{k}{2}\right \rceil$. For general $k$ and $t$, Li and Mao obtained a lower bound for $g(n,k,t)$ which is tight for the {case $k=3$.} We show that the bound also holds for $f(n,k,t)$ and is tight for the {case $k=3$.} When $t$ is general, we obtain upper bounds of both $f(n,k,t)$ and $g(n,k,t)$ for $k\in \{3,4,5\}$, and all of these bounds can be attained. When $k$ is general, we get an upper bound of $g(n,k,t)$ for $t\in \{1,2,3,4\}$ and an upper bound of $f(n,k,t)$ for $t\in \{1,2,3\}$. Moreover, both bounds can be attained.


generalized connectivity, tree connectivity, generalized $k$-connectivity, generalized $k$-edge-connectivity, packing