Wikipedia's article on the Reconstruction Conjecture mentions that the conjecture is false for digraphs, and refers to two papers by Stockmeyer. As far as I can see, none of the counter-examples in those papers are acyclic, so my question is

Can a directed acyclic graph be reconstructed from its deck of vertex-deleted subgraphs?

One has to assume the graph has at least $5$ vertices to avoid certain small cases. (Edit: For $4$ vertices, see Julian's example below.) Acyclic tournaments are reconstructible according to the references.

The question has an equivalent reformulation in representation theory:

Let $Q$ be a directed acyclic graph as above, and let $k$ be an algebraically closed field. Can the path algebra $\Lambda=kQ$ be reconstructed from its deck of vertex-deleted quotients $\Lambda/\Lambda e \Lambda$?

  • 5
    $\begingroup$ Nice question. There are actually two questions here, depending in whether the acyclicity is given or has to be inferred from the deck, but that is not an issue: for $n\ge 3$, $G$ is acyclic iff every vertex-deleted subgraph is acyclic and not all of them are paths. $\endgroup$ Aug 27, 2012 at 10:18
  • 4
    $\begingroup$ A related question is the reconstruction of posets. See for instance springerlink.com/content/q10314j8j0j721l8. $\endgroup$ Aug 27, 2012 at 23:35
  • $\begingroup$ The poset problem translated to the path algebra situation becomes the question whether $\Lambda$ is reconstructible from the deck of subalgebras $(1-e)\Lambda (1-e)$, where $e$ runs over all the trivial paths. $\endgroup$ Aug 28, 2012 at 6:28
  • $\begingroup$ Is there an additional meaning to the use of the word "deck" here that isn't carried by "set" (or maybe "multiset")? $\endgroup$ Dec 19, 2014 at 10:12
  • 1
    $\begingroup$ @QiaochuYuan: A deck is just a multiset. If the Deck Reconstruction Conjecture is equivalent to the Set Reconstruction Conjecture I think still is an open question. $\endgroup$ Dec 19, 2014 at 10:22

1 Answer 1


Brendan McKay's comment suggests that the following is true:

A vertex is a sink iff it is a sink in every vertex-deleted subgraph.

Assuming this, one can proceed as follows:

1) The directed acyclic graph can then be split as $Q'\stackrel{some arrows}{\to} sink $

2) deleting the sink gives you $Q'$

3) if there are at least two neighbours of the sink, you get the arrows between the sink and any neighbour by deleting each of the neighbours

4) if there is only one neighbour, there has to be another vertex (since there are at least 3 vertices), deleting this one, one gets the number of arrows between the neighbour and the sink.

  • $\begingroup$ This seems like a strategy, but how do you recognize the sink you have chosen in all subgraphs if there are several sinks? The same goes for recognizing the different neighbours. There is no labelling of the vertices. $\endgroup$ Aug 27, 2012 at 12:14
  • $\begingroup$ I have to think about that, I was assuming a labeling is given. $\endgroup$ Aug 27, 2012 at 12:20
  • 4
    $\begingroup$ For 4 vertices it is not possible then, take the square with the two possible non-cyclic orientations. $\endgroup$ Aug 27, 2012 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.