Timeline for From equivalent graphs to isomorphic one- Reconstruction Conjecture
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 10, 2021 at 18:30 | comment | added | LSpice | @FedorPetrov, indeed according to the current definition (it has been changing), so I think that's why one probably also wants to include something about multiplicity of spanning trees. The graphs in the counterexample of Sedláček satisfy this stronger notion of equivalence, but still are not isomorphic. | |
| Jan 9, 2021 at 23:52 | comment | added | Fedor Petrov | a cycle is equivalent to a path with the same number of vertices | |
| Jan 9, 2021 at 23:51 | vote | accept | Shahrooz | ||
| Jan 9, 2021 at 23:48 | history | edited | Shahrooz | CC BY-SA 4.0 |
deleted 44 characters in body; edited title
|
| Jan 9, 2021 at 23:40 | comment | added | LSpice | While @bof's comments on terminology are certainly apposite, surely this isn't what you meant. If you really wanted this asymmetric relation, then it is easy to come up with counterexamples: just take $H$ a non-tree, and $G$ a spanning tree of $H$. Surely what you meant was to consider the case where each spanning tree of $G$ is isomorphic to a spanning tree of $H$, and vice versa (possibly with multiplicity)? Anyway, the counterexample of Sedláček is a counterexample to this stronger condition. | |
| Jan 9, 2021 at 23:36 | history | edited | Shahrooz | CC BY-SA 4.0 |
added 22 characters in body
|
| Jan 9, 2021 at 23:19 | history | edited | Shahrooz | CC BY-SA 4.0 |
added 8 characters in body; edited title
|
| Jan 9, 2021 at 23:15 | comment | added | Shahrooz | @LSpice: you are right. Thanks for example. Actually, it is a good news. | |
| Jan 9, 2021 at 23:13 | comment | added | Shahrooz | @bof: you are right, and I have to change the word "equivalent ". But, if I have one of them, I am done. Since $P_4$ is ... to $K_4$ and RC is true for $P_4$, then it is true for other one. | |
| Jan 9, 2021 at 23:03 | comment | added | LSpice | Your question seems to ask whether two equivalent-in-your-sense graphs are isomorphic, and the answer (by Sedláček's article) is that they need not be. | |
| Jan 9, 2021 at 23:00 | answer | added | LSpice | timeline score: 7 | |
| Jan 9, 2021 at 22:53 | comment | added | Shahrooz | @LSpice: thanks for the reference. I saw the paper quickly. I do not want to construct the graphs by its spanning trees. I want to say if $G$ and $H$ are equivalent and $G$ is RC, then $H$ is RC. | |
| Jan 9, 2021 at 22:49 | comment | added | Jeremy Rickard | @LSpice The article is here. | |
| Jan 9, 2021 at 22:30 | comment | added | LSpice | Based on its MR review, Sedláček - The reconstruction of a graph from its spanning trees says no; but I can't find the original article. | |
| Jan 9, 2021 at 22:23 | history | asked | Shahrooz | CC BY-SA 4.0 |