tag:blogger.com,1999:blog-3722233.post5375461919331270157..comments2023-12-07T03:00:23.146-06:00Comments on Computational Complexity: Ref/info request for an obvious appraoch to GILance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-84071696793361630312014-06-16T22:15:00.827-05:002014-06-16T22:15:00.827-05:00I'll admit to not entirely following your nota...I'll admit to not entirely following your notation, Bill, but i'll take the opportunity to point out this paper by Steve Butler which gives methods to generate pairs of non-isomorphic graphs which share the same eigenvalues.<br /><br /><a href="http://www.combinatorics.org/Volume_18/PDF/v18i1p231.pdf" rel="nofollow">A construction of cospectral graphs for the normalized Laplacian</a><br /><br />The paper's results are focused on the normalized Laplacian matrix, but it includes techniques for several common graph matricesAndy Parrishhttps://www.blogger.com/profile/12252029594014518238noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7103265092100660402014-06-16T22:02:56.157-05:002014-06-16T22:02:56.157-05:00More generally, you can compute and compare the ch...More generally, you can compute and compare the characteristic polynomials [1] of the two input graphs. However, this graph polynomial is not complete, which means that there are non-isomorphic graphs with the same characteristic polynomial [1].<br /><br />[1] https://en.wikipedia.org/wiki/Characteristic_polynomialTyson Williamshttp://pages.cs.wisc.edu/~tdw/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53323280094835669072014-06-16T21:36:47.508-05:002014-06-16T21:36:47.508-05:001. The graph pair in page 3 of https://orion.math....1. The graph pair in page 3 of https://orion.math.iastate.edu/butler/PDF/spectra_lecture_1.pdf is a counter example. The determinant in both the cases are zero.<br /><br />2. GI is easy for most graphs. I would guess that this type of graphs of are also rare. <br /><br />bireswarhttps://www.blogger.com/profile/13113246066960630064noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32752291249091689852014-06-16T09:42:43.855-05:002014-06-16T09:42:43.855-05:00Threadjack. Do papers on unsuccessful approaches ...Threadjack. Do papers on unsuccessful approaches and attempts get published anymore? They seem useful.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33245358172715514402014-06-16T09:25:47.401-05:002014-06-16T09:25:47.401-05:00Frank Harary, The determinant of the adjacency mat... Frank Harary, The determinant of the adjacency matrix of a graph, SIAM Review, Vol. 4, No. 3. (Jul., 1962), pp. 202-210, It mentions counterexamples with 16 vertices by Bose and others but does not include them, saying that they will be "soon appear in the literature". These are likely strongly regular graphs of some sort. The natural reference is:<br /><br />Bose, R.C.: Strongly regular graphs, partial geometries and<br />partially balanced designs. Pacific J. Math., 13 (1963),<br /><br />but it is not online. In a later paper, Bose discusses a couple of non-isomorphic graphs on 16 vertices that seem to be the likely candidates but I haven't checked them:<br /><br />(a) Arrange the integers 1 through 16 corresponding to<br />the vertices of the graph in a 4 x 4 scheme.<br /> 1 2 3 4<br /> 5 6 7 8<br /> 9 10 11 12<br />13 14 15 16<br />Then any two vertices are adjacent if and only if the corresponding<br />integers are in the same row or same column.<br />(b) Arrange the integers corresponding to the vertices in a<br />4 x 4 scheme, and impose on it a cyclic Latin square. We thus obtain<br />1A 2B 3C 4D<br />5D 6A 7B 8C<br />9C 10D llA 12B<br />13B 14C 15D 16A<br />Two vertices are adjacent if they do not occur in the same row or<br />in the same column, and do not come together with the same letter<br />of the cyclic square.<br />Paul Beamehttp://www.cs.washington.edu/people/faculty/beame/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49688383908138291502014-06-16T09:00:09.769-05:002014-06-16T09:00:09.769-05:00It works poorly if the graph contains twin vertice...It works poorly if the graph contains twin vertices, for one...<br /><br />However, I have no idea about the general power of the scheme. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18124643457644022482014-06-16T08:45:52.943-05:002014-06-16T08:45:52.943-05:00Pretty sure we tried this years ago and it fails. ...Pretty sure we tried this years ago and it fails. <br /><br />dick liptonAnonymousnoreply@blogger.com