More on vertex-switching reconstruction (Q1322006)

A graph is called \(s\)-vertex switching reconstructible (\(s\)-VSR) if it is uniquely defined, up to isomorphism, by the multiset of unlabeled graphs obtained by switching of all its \(s\)-vertex subsets. Stanley proved that a graph with \(n\) vertices is \(s\)-VSR if the Krawtchouk polynomial \(P^ n_ s\) has no even roots. Solving balance equations for the switching reconstructing problem, we show that a graph is \(s\)-VSR if the corresponding Krawtchouk polynomial has one or two even roots laying far from \(n/2\). As a consequence we prove that graphs with sufficiently large number \(n\) of vertices are \(s\)-VSR for some values of \(s\) about \(n/2\). In particular, all graphs are \(s\)-VSR for \(n-2s=0,1,3\), and, if \(n\not\equiv 0\pmod 4\), for \(n-2s= 2,6\).