Degree conditions for vertex switching reconstruction (Q1126305)

This paper is related to the \(s\)-vertex switching reconstruction problem. If \(G= G(V,E)\) is a graph and \(U \subset V\), the switching \(G_U\) of \(G\) is the graph obtained from \(G\) by replacing all the edges between \(U\) and \(V \backslash U\) with the nonedges. The \(s\)-switching deck of \(G\), denoted \(D_s(G)\), is the multiset of unlabeled graphs \(\{G_U: |U |=s\}\), and \(G\) is \(s\)-vertex switching reconstructible if it is determined up to isomorphism by \(D_s(G)\). The Krawtchouck polynomials \(K^n_s\) are defined by \[ K^n_s = \sum^s_{i=0} (-1)^i{x \choose i} {n-x \choose s-i} \] and have proved useful in vertex switching problems. In particular, it is known that if \(K^n_s\) has no even integer roots, then any \(n\) vertex graph is \(s\)-vertex switching reconstructible. The results in this paper deal with the case when \(K^n_s\) has even roots. Let \(\delta\) and \(\Delta\) be the minimum and maximum degrees of an \(n\) vertex graph \(G\), and let \(2r\) and \(2R\) be the smallest and largest even integer roots of \(K^n_s\). The main result of this paper is that if \[ \min \left({n-1 \choose \Delta}, {n-1 \choose \delta} \right) < {2^{n-2} \over n \sqrt {n+1}} {n\choose R-r}^{-1/2} {n \choose R+r}^{-1/2} \] then \(G\) is \(s\)-vertex switching reconstructible. A corollary to this result that does not involve the roots \(R\) and \(r\) is also proved, and states that if \[ \min \left({n-1 \choose \Delta}, {n-1 \choose \delta} \right) < {2^{n-2} \over n\sqrt {n+1}} {n\choose t}^{-1/2} {n \choose n/2}^{-1/2} \] where \(t= \sqrt {(s-1)(n-s+2)}\), then \(G\) is \(s\)-vertex switching reconstructible.