The minimal size of a graph with generalized connectivity $κ_3 = 2$

Details The minimal size of a graph with generalized connectivity $κ_3 = 2$ The minimal size of a graph with generalized connectivity $κ_3 = 2$

2011-01-20

arxiv.org/abs/1101.3811v3

Mathematics

Combinatorics

9 pages

Scientific paper

Let $G$ be a nontrivial connected graph of order $n$ and $k$ an integer with $2\leq k\leq 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\leq i,j\leq \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)\geq 6/5v(G)$, and the lower bound is sharp by showing a class of examples attaining the lower bound.

Affiliated with

Also associated with

No associations

Rating

The minimal size of a graph with generalized connectivity $κ_3 = 2$ does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The minimal size of a graph with generalized connectivity $κ_3 = 2$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The minimal size of a graph with generalized connectivity $κ_3 = 2$ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-332930