4
$\begingroup$

I have seen this question asked at least once before, but not with any real answers.

I was reading about the various reconstruction conjectures and equivalents, and I saw that the reconstruction conjecture, which uses a multi-set, has a set counterpart, the set reconstruction conjecture.

My question is: Does the edge reconstruction conjecture have a similar statement that involves the set and not the multi-set? Perhaps the minimum of four edges still applies? I've been curious about this for some time now and can't seem to reach a decisive conclusion.

Any help is appreciated!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The edge-reconstruction conjecture does have an analogous statement to the set version of the reconstruction conjecture. As far as I am aware there is no graphs that are edge-reconstructible but not "set edge-reconstructible". Therefore the corresponding conjecture would (probably) state that every graph with at least four edges is set edge-reconstructible.

A few things relating to this problem have been done. First a theorem by Manvel:

Theorem: (in [1, Theorem 9]) The degree sequence of a graph is a set edge-reconstructible property.

Interestingly, Manvel also states that Hemminger's proof (1969) that edge-reconstruction is a special case of vertex-reconstruction extends to the case where we consider sets instead of multisets. However, there seems to be no set analogue of Greenwell's theorem that states that any vertex-reconstructible graph without isolated vertices also is edge-reconstructible.

Theorem: (in [2]) A graph with at least four edges is set edge-reconstructible if the set of edge-deleted subgraphs has size at most two.

[1] B. Manvel, "On reconstructing graphs from their sets of subgraphs", J. Comb. Theory B 21(2), (1976), 156-165.

[2] L.D. Andersen, S. Ding, P.B. Vestergaard, "On the set edge-reconstruction conjecture", JCMCC - Journal of Combinatorial Mathematics and Combinatorial Computing 20 (1996), 3-9.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you very much for your answer! This helps tremendously. And you even addressed my next question which was about Greenwell's theorem. Would you happen to know if anyone has attempted a set analogue to the theorem? I don't see why there couldn't be one, but that could be because I have not made a serious attempt at it. $\endgroup$
    – Brian Frazier
    Commented Jan 15, 2016 at 22:31
  • $\begingroup$ @BrianFrazier I don't know of any attempt at the set analogue of Greenwell's theorem. There does not seem to be much work done on set edge-reconstruction, at least that I have found. It is an interesting problem though. The problem seems to be the use of "subgraph counting" (e.g. Kelly's lemma). Note also that if there were an analogue of Kelly's lemma for set edge-reconstruction then set edge-reconstuction and (multiset) edge-reconstruction would be equivalent since then you would be able to recreate the full edge-deck from the set of edge-deleted subgraphs. $\endgroup$
    – Oliver Krüger
    Commented Jan 17, 2016 at 18:46
  • $\begingroup$ That's very interesting. I found the same result in my searches. Set edge-reconstruction doesn't seem to be very well studied. I don't know if it is because it isn't worth pursuing or because getting results becomes difficult. Your note on Kelly's lemma is very interesting as well. I hadn't noticed that implication. I appreciate your help and insights on this topic! $\endgroup$
    – Brian Frazier
    Commented Jan 19, 2016 at 19:42
  • $\begingroup$ Just as vertex reconstruction implies set reconstruction, a natural question is does set vertex reconstruction imply set edge reconstruction? $\endgroup$
    – Jérôme JEAN-CHARLES
    Commented Jun 4, 2017 at 23:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .