Reconstruction of a graph of order \(p\) from its \((p-1)\)-complements (Q1917719)

Let \(G=(V,E)\) be a graph of order \(p\geq 2\) and let \(P=\{V_1,\dots,V_{p-1}\}\) be a partition of \(V\) of order \(p-1\), i.e., the \(V_i\) are disjoint subsets of \(V\) such that \(|V_i|=2\) for exactly one \(V_i\) and \(|V_j|= 1\) for all \(j\neq i\). Then the \((p-1)\)-complement of \(G\) with respect to \(P\) is defined as follows: For all \(V_k\) and \(V_j\) in \(P\), \(k\neq j\), remove the edges between \(V_k\) and \(V_j\), and add the missing edges between them. The authors conjecture that all graphs are reconstructible from the collection of all its \((p-1)\)-complements and verify the correctness of this conjecture for all disconnected, all unicyclic, and all bipartite graphs.