More on Vertex-Switching Reconstruction

✍ Scribed by I. Krasikov; Y. Roditty

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 596 KB
• Volume: 60
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1994.1004

✦ Synopsis

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_{s}^{n}) has no even roots. Solving balance equations, introduced in Krasnikov and Roditty (Arch. Math. (Basel) 48 (1987), 458-464) for the switching reconstruction 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-2 s=0,1,3), and if (n \neq 0(\bmod 4)), for (n-2 s=2,6). % 1994 Academic Press. Inc.