The characterization conjecture for uniquely C4+C_{4}^{+}-saturated graphs

From papers

Let C4+C_{4}^{+} be the diamond graph consisting of a 44-cycle with one chord, and let C3C_{3}^{*} be the graph consisting of a triangle with a pendant edge. A graph is strongly regular with parameters (n,k,0,2)(n,k,0,2) if it has nn vertices, is kk-regular, every adjacent pair has no common neighbor, and every nonadjacent pair has exactly two common neighbors. A graph is nontrivial uniquely C4+C_{4}^{+}-saturated if it is C4+C_{4}^{+}-free and adding any missing edge creates exactly one copy of C4+C_{4}^{+}, with at least four vertices.

Uniquely C4+C_{4}^{+}-saturation conjecture. A graph GG is nontrivial uniquely C4+C_{4}^{+}-saturated if and only if GG is a strongly regular graph with parameters (n,k,0,2)(n,k,0,2) or GC3G\cong C_{3}^{*}.

The conjecture proposes a complete classification of these graphs. The source establishes the one-triangle case and rules out graphs with two, three, or four triangles, but leaves the possibility of more than four triangles unresolved.

Progress summary

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

Sources & referencesView supporting material

Primary source

Yuying Li, Kexiang Xu, Dániel Gerbner and Wenzhong Liu, “Uniquely C_4^+-saturated graphs”, arXiv:2412.17962 (2024).

Solutions 0

No solutions have been posted yet.