pipette
ENEnglish

The maximum number of triangles in regular graphs

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

Preprint

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.