| Titel | Cospectral Graphs and Regular Orthogonal Matrices of Level 2 |
|---|---|
| Gepubliceerd in | CentER Discussion Paper, Vol. 2012-042. |
| Auteur | Abiad, A.; Haemers, W.H. |
| Datum | 2012 |
| Trefwoord(en) | cospectral graphs, orthogonal matrices, switching. |
| Type | working paper |
| Uitgever | Tilburg University. Center for Economic Research |
| Samenvatting | Abstract: For a graph Γ with adjacency matrix A, we consider a switching operation that takes Γ into a graph Γ' with adjacency matrix A', defined by A' = QtAQ, where Q is a regular orthogonal matrix of level 2 (that is, QtQ = I, Q1 = 1, 2Q is integral, and Q is not a permutation matrix). If such an operation exists, and Γ is nonisomorphic with Γ', then we say that Γ' is semi-isomorphic with Γ. Semiisomorphic graphs are R-cospectral, which means that they are cospectral and so are their complements. Wang and Xu [‘On the asymptotic behavior of graphs determined by their generalized spectra’, Discrete Math. 310 (2010)] expect that almost all pairs of R-cospectral graphs are semi-isomorphic. Regular orthogonal matrices of level 2 have been classified. By use of this classification we work out the requirements for this switching operation to work in case Q has one nontrivial indecomposable block of size 4, 6, 7 or 8. Size 4 corresponds to Godsil-McKay switching. The other cases provide new methods for constructions of R-cospectral graphs. For graphs with eight vertices all these constructions are carried out. As a result we find that, out of the 1166 graphs on eight vertices which are R-cospectral to another graph, only 44 are not semi-isomorphic to another graph. |
| Publicatie | http://repository.uvt.nl/id/ir-uvt-nl:oai:wo.uvt.nl:5539329 |
| Persistent Identifier | urn:nbn:nl:ui:12-5539329 |
| Metadata | XML |
| Repository | Tilburg University |
Omhoog
Ga terug naar de inhoud
Ga terug naar de site navigatie