Cambie–de Verclos–Kang conjecture on triangles in regular graphs

For positive integers nn and kk, let t(n,k)t(n,k) be the minimum number of triangles over all kk-regular graphs on nn vertices. Let G(n,k)\mathcal{G}(n,k) denote the family of extremal graphs referred to in the source.

Cambie–de Verclos–Kang conjecture. For every odd integer nn and even integer kk with

2n5<k<n2,\frac{2n}{5}< k< \frac{n}{2}, t(n,k)=k4(3kn1).t(n,k)=\frac{k}{4}(3k-n-1).

Moreover, the extremal graphs must belong to G(n,k)\mathcal{G}(n,k).

This conjecture seeks the exact minimum number of triangles in regular graphs in the range above, together with a characterization of all extremal graphs. The paper records it as a conjecture of Cambie, de Joannis de Verclos, and Kang; the supplied material gives no resolution.

Sources & referencesView supporting material

Primary source

Jialin He, Xinmin Hou, Jie Ma and Tianying Xie, “Counting triangles in regular graphs”, arXiv:2309.02993 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.