Extremal problems on saturation for the family of $k$-edge-connected graphs

Abstract

Let $\mathcal{F}$ be a family of graphs. A graph $G$ is $\mathcal{F}$-saturated if $G$ contains no member of $\mathcal{F}$ as a subgraph but $G+e$ contains some member of $\mathcal{F}$ whenever $e\in E(\overline{G})$. The saturation number and extremal number of $\mathcal{F}$, denoted $sat(n,\mathcal{F})$ and $ex(n,\mathcal{F})$ respectively, are the minimum and maximum numbers of edges among $n$-vertex $\mathcal{F}$-saturated graphs. For $k\in \mathbb{N}$, let ${\mathcal{F}}_k$ and ${\mathcal{F}}_k^{\prime }$ be the families of $k$-connected and $k$-edge-connected graphs, respectively. Wenger proved $sat(n,{\mathcal{F}}_k)=(k-1)n-\left(\genfrac{}{}{0ex}{}{k}{2}\right)$, we prove $sat(n,{\mathcal{F}}_k^{\prime })=(k-1)(n-1)-\lfloor \frac{n}{k+1}\rfloor \left(\genfrac{}{}{0ex}{}{k-1}{2}\right)$. We also prove $ex(n,{\mathcal{F}}_k^{\prime })=(k-1)n-\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ and characterize when equality holds. Finally, we give a lower bound on the spectral radius for ${\mathcal{F}}_k$-saturated and ${\mathcal{F}}_k^{\prime }$-saturated graphs.

arXiv comment9 pages, we welcome any comments and suggestions