pith. sign in

arxiv: 1106.4411 · v1 · pith:WAXUKLQ5new · submitted 2011-06-22 · 🧮 math.CO

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

classification 🧮 math.CO
keywords graphkappaboundlowerordersizeconnectivitygeneralized
0
0 comments X
read the original 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)\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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.