Note on the minimal size of a graph with generalized connectivity kappa_3= 2

Details Note on the minimal size of a graph with generalized connectivity kappa_3= 2 Note on the minimal size of a graph with generalized connectivity kappa_3= 2

2011-06-22

arxiv.org/abs/1106.4411v1

Mathematics

Combinatorics

7 pages

Scientific paper

The concept of generalized $k$-connectivity $\kappa_{k}(G)$ of a graph $G$ was introduced by Chartrand et al. in recent years. In our early paper, extremal theory for this graph parameter was started. We determined the minimal number of edges of a graph of order $n$ with $\kappa_{3}= 2$, i.e., for a graph $G$ of order $n$ and size $e(G)$ with $\kappa_{3}(G)= 2$, we proved that $e(G)\geq (6/5)n$, and the lower bound is sharp by constructing a class of graphs, only for $n\equiv 0 \ (mod \ 5)$ and $n\neq 10$. In this paper, we improve the lower bound to $\lceil(6/5)n\rceil$. Moreover, we show that for all $n\geq 4$ but $n= 9, 10$, there always exists a graph of order $n$ with $\kappa_{3}= 2$ whose size attains the lower bound $\lceil(6/5)n\rceil$. Whereas for $n= 9, 10$ we give examples to show that $\lceil(6/5)n\rceil+1$ is the best possible lower bound. This gives a clear picture on the minimal size of a graph of order $n$ with generalized connectivity $\kappa_{3}= 2$.

Affiliated with

Also associated with

No associations

Rating

Note on the minimal size of a graph with generalized connectivity kappa_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 Note on the minimal size of a graph with generalized connectivity kappa_3= 2, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Note on the minimal size of a graph with generalized connectivity kappa_3= 2 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-205729