Why is the edge reconstruction conjecture stated with the deck defined as the multi set of graphs formed by deleting one edge? Can someone give an example of two graphs such that the edge deleted subgraph set is the same but the multi set is different?
$\begingroup$
$\endgroup$
5
asked Jul 24, 2014 at 12:04
-
$\begingroup$ Your vertex example has a problem: $3n$ vertices versus $3n-3$ vertices. $\endgroup$– Brendan McKayCommented Jul 24, 2014 at 13:36
-
$\begingroup$ Thank you, i realised it doesn't work (even if i hadn't made the mistake of writ in n-2 instead of n-1). It only gives subgraphs of n copies of $K_{1,2} \subset$ subgraphs of (n-1 copies of $K_{1,2} \cup K_1 \cup K_2$), the reverse isn't true. $\endgroup$– Thinniyam Srinivasan RamanathaCommented Jul 25, 2014 at 6:57
-
$\begingroup$ @DagOskarMadsen But the set reconstruction is stated only for vertex right? What about edge reconstruction? Is there a set version for that as well? $\endgroup$– Thinniyam Srinivasan RamanathaCommented Aug 13, 2014 at 8:09
-
$\begingroup$ Sorry, you are right. I will delete my comment. $\endgroup$– Dag Oskar MadsenCommented Aug 13, 2014 at 8:54
-
$\begingroup$ Are you asking if there is a difference between a set of edge-deleted subgraphs and a multi-set of edge deleted subgraphs? If so, a multi-set is a set-like object in which order is ignored, but multiplicity is explicitly significant. Therefore {a,a,b} and {a,b} are distinct in multisets but both will be considered as {a,b} in sets. mathworld.wolfram.com (Wolfram Mathworld) $\endgroup$– user94793Commented Jul 7, 2016 at 4:12
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Harary conjectured that the set of vertex deleted subgraphs is unique up to isomorphism. (On the reconstruction of a graph from a collection of subgraphs. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 47–52.)
If you could find an example, you would have proven Haray's strong reconstruction conjecture false. This is because if the vertex reconstruction conjecture is true, then the edge reconstruction conjecture is true, thus the same would hold for the set versions.
-
$\begingroup$ I know the result that deck is reconstructible from edge deck, but is the same true for the sets? $\endgroup$ Commented Dec 18, 2014 at 6:01
$\begingroup$
$\endgroup$
The two problems you mention are not the same, though it is obvious that one implies the other. Nobody knows if they are equivalent. Probably the reason that the "set" version is less known is that it seems to be harder than the "multiset" version version that has already proved too difficult for the many people who have worked on it.
answered Jul 7, 2016 at 4:22