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\).
- A note on the vertex-switching reconstruction
- Degree conditions for vertex switching reconstruction
- Vertex-switching reconstruction and folded cubes
- Applications of balance equations to vertex switching reconstruction
- Switching reconstruction of digraphs
- Integer zeros of \(q\)-Krawtchouk polynomials in classical combinatorics
- Switching reconstruction and diophantine equations
This page was built for publication: More on vertex-switching reconstruction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1322006)
