pipette
ESEspañol

The maximum number of triangles in regular graphs

Ya-Hong Chen, Shi-Cai Gong, Changhong Lu, Zhuojie Tu, Long-Tu Yuan

Preprint

In the authors' words

We determine the maximum number of triangles in -vertex -regular graphs and characterize all extremal graphs for all admissible orders when is odd and for an explicit range of orders when is even. For even , 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 -regular graphs and characterize all equality cases. Our exact results confirm the conjecture of Petingi and Rodr\'iguez and the triangle case of a conjecture of Cambie, de Joannis de Verclos and Kang for all odd and the specified orders when is even. Moreover, for every even , we construct counterexamples to both conjectures and obtain a recursive characterization of all extremal graphs of order at least , where is an absolute constant.

Main resultLimitation the authors admit

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.