The maximum number of triangles in a graph of given maximum degree

DOI10.19086/AIC.16788MaRDI QIDQ5126762zbMATH OpenOpenAlexFDO

Authors Zachary Chase

Publication date 20 October 2020

Published in Advances in Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Gan-Loh-Sudakov conjecture

Mathematics Subject Classification ID

Vertex degrees (05C07) Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We prove that any graph on $n$ vertices with max degree $d$ has at most $qd+1choose3+rchoose3$ triangles, where $n=q(d+1)+r$, $0lerled$. This resolves a conjecture of Gan-Loh-Sudakov.

Recommendations

• Many triangles with few edges
• scientific article; zbMATH DE number 1866931
• Maximal triangle‐free graphs with restrictions on the degrees
• Size and independence in triangle‐free graphs with maximum degree three
• scientific article; zbMATH DE number 721637

Cited in

(24)

• Maximum vertex and face degree of oblique graphs
• Many cliques with few edges and bounded maximum degree
• The maximum number of induced open triangles in graphs of a given order
• A simple proof of the Gan-Loh-Sudakov conjecture
• Supersaturation for subgraph counts
• Generalized Turán number for linear forests
• Many cliques with few edges
• The maximum number of complete subgraphs of fixed size in a graph with given maximum degree
• On the Maximum Number of Triangles in Wheel-Free Graphs
• scientific article; zbMATH DE number 1866931 (Why is no real title available?)
• Tree densities in sparse graph classes
• On the maximum number of open triangles in graphs with the same number of vertices and edges
• The maximum number of triangles in \(F_k\)-free graphs
• Regular Turán numbers and some Gan–Loh–Sudakov‐type problems
• Maximum cliques in a graph without disjoint given subgraph
• Many Cliques in Bounded-Degree Hypergraphs
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• Exact results on generalized Erdős-Gallai problems
• A note on the generalized Turán number of star forests
• Counting multiple graphs in generalized Turán problems
• Extremal problems for a matching and any other graph
• On the generalized Turán number of star forests
• The generalized Turán number of 4S_
• Efficient enumeration of cliques in graphs with bounded maximum degree

This page was built for publication: The maximum number of triangles in a graph of given maximum degree

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