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

Abstract

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)\ge (6/5)n$, and the lower bound is sharp by constructing a class of graphs, only for $n\equiv 0(mod5)$ and $n\ne 10$. In this paper, we improve the lower bound to $\lceil (6/5)n\rceil$. Moreover, we show that for all $n\ge 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$.

7 pages