The characterization conjecture for uniquely -saturated graphs
Let be the diamond graph consisting of a -cycle with one chord, and let be the graph consisting of a triangle with a pendant edge. A graph is strongly regular with parameters if it has vertices, is -regular, every adjacent pair has no common neighbor, and every nonadjacent pair has exactly two common neighbors. A graph is nontrivial uniquely -saturated if it is -free and adding any missing edge creates exactly one copy of , with at least four vertices.
Uniquely -saturation conjecture. A graph is nontrivial uniquely -saturated if and only if is a strongly regular graph with parameters or .
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
- Yuying Li, Kexiang Xu, Dániel Gerbner and Wenzhong Liu, “Uniquely C_4^+-saturated graphs”, arXiv:2412.17962 (2024).
Progress summary
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.