Triangles in K_s-saturated graphs with minimum degree t

DOI10.20429/TAG.2020.070102zbMATH Open1441.05117arXiv1906.02154OpenAlexW3010229460MaRDI QIDQ5113451FDOQ5113451

Authors: Craig Timmons, Benjamin Cole, Albert Curry, David Davini 

Publication date: 11 June 2020

Published in: Theory and Applications of Graphs (Search for Journal in Brave)

Abstract: For $ngeq15$, 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, ErdH{o}s, Holzman, and Krivelevich from 1996. Additionally, we show that for any $s>rgeq3$ and $tgeq2(s-2)+1$, there is a $K_s$-saturated $n$-vertex graph with minimum degree $t$ that has $$ 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.

Full work available at URL: https://arxiv.org/abs/1906.02154

Recommendations

• Saturated graphs of prescribed minimum degree
• Onk-saturated graphs with restrictions on the degrees
• Minimalk-saturated and color critical graphs of prescribed minimum degree
• Minimum degree and the minimum size of \(K_2^t\)-saturated graphs
• MinimumK_{2, 3}-Saturated Graphs

zbMATH Keywords

minimum number of triangles in an \(n\)-vertex \(K_4\)-saturated graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Enumeration in graph theory (05C30)

Cited In (5)

• Onk-saturated graphs with restrictions on the degrees
• Title not available (Why is that?)
• Minimum degree and the minimum size of \(K_2^t\)-saturated graphs
• MinimumK_{2, 3}-Saturated Graphs
• \(K_r\)-saturated graphs and the two families theorem

This page was built for publication: Triangles in \(K_s\)-saturated graphs with minimum degree \(t\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113451)