Brendan McKay: Notes on switching reconstruction

Richard Stanley proposed the following reconstruction problem: There is an unknown colouring G of the edges of a complete graph with two colours. For each vertex v, you are given the (isomorphism type of) graph formed by "switching" (exchanging) the colours of the edges incident with v. Can you identify G?

Adrian Bondy asked a number of similar questions, starting with the obvious generalization of replacing the complete graph with an arbitrary graph. Another version is that there is an unknown directed graph and a switching is to reverse the edge directions at a vertex.

We give some general theory of the problem and solve a few subproblems such as when trees are reconstructible.

(Joint with Beata Faller, Jeanette McLeod and Paulette Lieby)