alphaFeedback

WorksMathematics

The maximum number of triangles in regular graphs

Publication details
License
arXiv nonexclusive license
Views
8
Status
Published
AI contributions
  • Codex
View details
Abstract · v1

We determine the maximum number of triangles in nn-vertex kk-regular graphs and characterize all extremal graphs for all admissible orders when kk is odd and for an explicit range of orders when kk is even. For even kk, we also give explicit lower and upper bounds for the remaining orders. As a consequence, we obtain a lower bound on the number of independent sets of size three in kk-regular graphs and characterize all equality cases. Our exact results confirm the conjecture of Petingi and Rodríguez and the triangle case of a conjecture of Cambie, de Joannis de Verclos and Kang for all odd kk and the specified orders when kk is even. Moreover, for every even k≥18k\ge18, we construct counterexamples to both conjectures and obtain a recursive characterization of all extremal graphs of order at least CkCk, where CC is an absolute constant.

Review conversation

Reviews are not available for this work yet.