Timeline for Is a connected graph uniquely determined by its weighted 2-step graph?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Aug 4, 2014 at 13:14 | vote | accept | Paul Siegel | ||
| Aug 1, 2014 at 17:48 | answer | added | user56203 | timeline score: 3 | |
| Aug 1, 2014 at 15:42 | history | migrated | from math.stackexchange.com (revisions) | ||
| Jul 26, 2014 at 23:33 | comment | added | Paul Siegel | @GerryMyerson I had the same thought and even checked some examples of isospectral graphs that I found online, with no success. But as Studentmath pointed out this question is in a sense about characterizing square roots of certain matrices, so spectral theory seem relevant. | |
| Jul 26, 2014 at 23:21 | comment | added | Gerry Myerson | I wonder whether there is anything to be learned from isospectral graphs? | |
| Jul 26, 2014 at 23:15 | comment | added | Gerry Myerson | I think I misunderstood the problem. Sorry. | |
| Jul 26, 2014 at 15:15 | comment | added | Paul Siegel | @Studentmath That is true in the sense that the adjacency matrix of the $2$-step graph is the square of the adjacency matrix of the original graph. But to turn it into a straight linear algebra problem you must include the condition that the irreducible $0-1$ matrices are symmetric ($G$ and $H$ are undirected) and have $0$'s along the diagonal ($G$ and $H$ are simple). | |
| Jul 26, 2014 at 15:10 | comment | added | Paul Siegel | @GerryMyerson Do you have a specific polynomial time algorithm in mind for determining whether or not the $2$-step graphs are isomorphic? As far as I can tell the isomorphism problem for the $2$-step graphs is just as hard (maybe harder?) than the isomorphism problem for the original graphs. | |
| Jul 26, 2014 at 8:56 | comment | added | Studentmath | Correct me if I am wrong, but this is equivalent to asking whether two different irreducible, 0-1 matrices may have the same equivalent $A^2$ matrix? | |
| Jul 26, 2014 at 8:53 | comment | added | Gerry Myerson | If connected graphs were so easily determined, the isomorphism problem for them would be decided in polynomial time --- but that's widely believed to be impossible, so surely there are counterexamples. | |
| Jul 26, 2014 at 8:14 | comment | added | Paul Siegel | @Studentmath Yes. | |
| Jul 26, 2014 at 8:07 | comment | added | Studentmath | You would like an example with simple graphs, I assume? | |
| Jul 26, 2014 at 7:40 | history | asked | Paul Siegel | CC BY-SA 3.0 |