Uniquely \(K_r\)-saturated graphs (Q1953308)

Summary: A graph \(G\) is uniquely \(K_r\)-saturated if it contains no clique with \(r\) vertices and if for all edges \(e\) in the complement, \(G+e\) has a unique clique with \(r\) vertices. Previously, few examples of uniquely \(K_r\)-saturated graphs were known, and little was known about their properties. We search for these graphs by adapting orbital branching, a technique originally developed for symmetric integer linear programs. We find several new uniquely \(K_r\)-saturated graphs with \(4 \leq r \leq 7\), as well as two new infinite families based on Cayley graphs for \(\mathbb{Z}_n\) with a small number of generators.