Notes on switching reconstruction

Graphs, Hypergraphs, and Computing

18 March 14:00 - 15:00

Brendan McKay - Australian National University

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)
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to