Reconstruction from vertex-switching (Q1062077)

Vertex-switching at vertex \(v\) in graph \(X\) is accomplished by deleting all edges of \(X\) incident with v and inserting all edges of the complement of \(X\) that are incident with \(v\). If we denote this graph by \(X_ v\) the author considers the vertex-switching reconstruction problem: Is \(X\) determined, up to isomorphisms, by the unlabelled graphs \(X_ v\), \(v\in V(X)\)? Via \(4K_ 1\) and \(C_ 4\), the answer is negative for \(n=4\) and it is still an open question for \(n=4k\), \(k>1\). A technique from linear algebra is used as follows to give an affirmative answer when \(n\not\equiv 0 (\bmod 4).\) Let \({\mathcal G}_ n\) denoe the set of all graphs on the vertex set \(\{x_ 1,x_ 2,...,x_ n\}\) and let \({\mathcal V}_ n\) denote the real vector space of all formal linear combinations \(\sum_{X\in {\mathcal G}_ n}a_ X\), \(a_ X\in R\). Define the linear transformation \(\Phi\) : \({\mathcal V}_ n\to {\mathcal V}_ n\) by \(\Phi(X)=X_ 1+X_ 2...+X_ n\) where \(X_ i\) is the labelled vertex-switched graph of X at vertex \(x_ i\). The author then proves that the linear transformation \(\Phi\) is invertible if and only if \(n\not\equiv 0 (mod 4).\) He next introduces an equivalence relation that in essence unlabels X and easily gives \([X]=[X']\) if and only if \(X\simeq X\). The proof of the theorem is completed for \(n\not\equiv 0 (\bmod 4)\) by showing that \(\Phi[X]=\Phi[X']\). He then indicates a generalization to the graphs obtained by switching on the i-element subsets of \(V(X)\) and closes by asking for a proof that explicitly describes the recontructed graph \(X\) as well as for a resolution of the \(n\equiv 0 (\bmod 4)\) case.