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

At least 1 year old · documented by

Let C4+C_{4}^{+} be the diamond graph consisting of a 44-cycle with one chord, and let C3∗C_{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 G≅C3∗G\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.

References

Primary source

Yuying Li, Kexiang Xu, Dániel Gerbner and Wenzhong Liu, “Uniquely C_4^+-saturated graphs”, arXiv:2412.17962 (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.