pith. sign in

arxiv: 1906.02154 · v1 · pith:3YWJMNDYnew · submitted 2019-06-05 · 🧮 math.CO

Triangles in K_s-saturated graphs with minimum degree t

classification 🧮 math.CO
keywords minimumdegreegraphsaturatednumbertheretrianglesvertex
0
0 comments X
read the original abstract

For $n \geq 15$, we prove that the minimum number of triangles in an $n$-vertex $K_4$-saturated graph with minimum degree 4 is exactly $2n-4$, and that there is a unique extremal graph. This is a triangle version of a result of Alon, Erd\H{o}s, Holzman, and Krivelevich from 1996. Additionally, we show that for any $s > r \geq 3$ and $t \geq 2 (s-2)+1$, there is a $K_s$-saturated $n$-vertex graph with minimum degree $t$ that has $\binom{ s-2}{r-1}2^{r-1} n + c_{s,r,t}$ copies of $K_r$. This shows that unlike the number of edges, the number of $K_r$'s ($r >2$) in a $K_s$-saturated graph is not forced to grow with the minimum degree, except for possibly in lower order terms.

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.