Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Triangles In Ks-Saturated Graphs With Minimum Degree T, Craig Timmons, Benjamin Cole, Albert Curry, David Davini
Triangles In Ks-Saturated Graphs With Minimum Degree T, Craig Timmons, Benjamin Cole, Albert Curry, David Davini
Theory and Applications of Graphs
For n ≥ 15, we prove that the minimum number of triangles in an n-vertex K4-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, Erdos, Holzman, and Krivelevich from 1996. Additionally, we show that for any s > r ≥ 3 and t ≥ 2 (s-2)+1, there is a Ks-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 Kr. This shows that …