The minimal size of a graph with generalized connectivity ${\kappa }_3=2$

Abstract

Let $G$ be a nontrivial connected graph of order $n$ and $k$ an integer with $2\le k\le n$. For a set $S$ of $k$ vertices of $G$, let $\kappa (S)$ denote the maximum number $\ell$ of edge-disjoint trees $T_1,T_2,...,T_{\ell }$ in $G$ such that $V(T_i)\cap V(T_j)=S$ for every pair $i,j$ of distinct integers with $1\le i,j\le \ell$. Chartrand et al. generalized the concept of connectivity as follows: The $k$-$connectivity$, denoted by ${\kappa }_k(G)$, of $G$ is defined by ${\kappa }_k(G)=$min$\{\kappa (S)\}$, where the minimum is taken over all $k$-subsets $S$ of $V(G)$. Thus ${\kappa }_2(G)=\kappa (G)$, where $\kappa (G)$ is the connectivity of $G$. This paper mainly focuses on the minimal number of edges of a graph $G$ with ${\kappa }_3(G)=2$. For a graph $G$ of order $v(G)$ and size $e(G)$ with ${\kappa }_3(G)=2$, we obtain that $e(G)\ge 6/5v(G)$, and the lower bound is sharp by showing a class of examples attaining the lower bound.

9 pages

Cited by in corpus (5)

• On the generalized (edge-)connectivity of graphs
• A survey on the generalized connectivity of graphs
• The generalized 3-connectivity of random graphs
• The generalized 3-(edge) connectivity of total graphs
• Two bounds for generalized $3$-connectivity of Cartesian product graphs