The characterization conjecture for uniquely -saturated graphs
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.
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
Sign in to submit a solution.
No solutions have been posted yet.