Triangles in K_s-saturated graphs with minimum degree t

DOI10.20429/TAG.2020.070102MaRDI QIDQ5113451zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cited in

(5)

• Onk-saturated graphs with restrictions on the degrees
• scientific article; zbMATH DE number 3865320 (Why is no real title available?)
• 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)