Recognition: unknown
Extremal problems on saturation for the family of k-edge-connected graphs
read the original 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$ be the families of $k$-connected and $k$-edge-connected graphs, respectively. Wenger proved $sat(n,\mathcal{F}_k)=(k-1)n-{k\choose2}$, we prove $sat(n,\mathcal{F}'_k)=(k-1)(n-1)-\lfloor{\frac {n}{k+1}}\rfloor{k-1 \choose 2}$. We also prove $ex(n,\mathcal{F}'_k)=(k-1)n-{k\choose2}$ and characterize when equality holds. Finally, we give a lower bound on the spectral radius for $\mathcal{F}_k$-saturated and $\mathcal{F}'_k$-saturated graphs.
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.