Dong–Luo Conjecture on Tight (k,0)-Stable Graphs

Dong and Luo posed the question in 2024: for sufficiently large $k$, the only tight $(k,0)$-stable graphs should be $K_{k+1}$ and $K_{k+2}$. The conjecture concerns the structure of extremal stable graphs.

Known results

• Dong and Luo, 2024: every tight $(2,0)$-stable graph of odd order is an odd cycle.
• Dong and Luo, 2024: every tight $(k,0)$-stable graph has at most $k+6$ vertices for $k\geq 3$.
• Liu, Song, and Wang, 2024: for $k\geq 24$, the only examples are $K_{k+1}$ and $K_{k+2}$.

August 2026 claimed classification

Xu, Yuqi, Yang, Weihua, Guan, and Xiaxia claim an author proof for all $k\geq 4$. For $k\geq 5$, only $K_{k+1}$ and $K_{k+2}$ occur; for $k=4$, the list is $K_5$, $K_6$, $H_8^1$, $H_8^2$, and $H_8^3$. This extends the previous $k\geq 24$ result, but independent verification is absent.

Current status (as of August 2026): The conjecture is claimed resolved for all $k\geq 4$, including the explicit $k=4$ cases, but the classification remains unverified pending independent checking.