Cospectral Graphs and Regular Orthogonal Matrices of Level 2

A. Abiad, W.H. Haemers

Research output: Working paperDiscussion paperOther research output

259 Downloads (Pure)

Abstract

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.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages16
Volume2012-042
Publication statusPublished - 2012

Publication series

NameCentER Discussion Paper
Volume2012-042

Fingerprint

Cospectral Graphs
Orthogonal matrix
Graph in graph theory
Isomorphic
Adjacency Matrix
Permutation Matrix
Discrete Spectrum
Complement
Asymptotic Behavior

Keywords

  • cospectral graphs
  • orthogonal matrices
  • switching

Cite this

Abiad, A., & Haemers, W. H. (2012). Cospectral Graphs and Regular Orthogonal Matrices of Level 2. (CentER Discussion Paper; Vol. 2012-042). Tilburg: Operations research.
Abiad, A. ; Haemers, W.H. / Cospectral Graphs and Regular Orthogonal Matrices of Level 2. Tilburg : Operations research, 2012. (CentER Discussion Paper).
@techreport{c656ae2cdc8344be906cb93e5ab191a4,
title = "Cospectral Graphs and Regular Orthogonal Matrices of Level 2",
abstract = "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.",
keywords = "cospectral graphs, orthogonal matrices, switching",
author = "A. Abiad and W.H. Haemers",
note = "Subsequently published in the Electronic Journal of Combinatorics (2012) Pagination: 16",
year = "2012",
language = "English",
volume = "2012-042",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

Abiad, A & Haemers, WH 2012 'Cospectral Graphs and Regular Orthogonal Matrices of Level 2' CentER Discussion Paper, vol. 2012-042, Operations research, Tilburg.

Cospectral Graphs and Regular Orthogonal Matrices of Level 2. / Abiad, A.; Haemers, W.H.

Tilburg : Operations research, 2012. (CentER Discussion Paper; Vol. 2012-042).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Cospectral Graphs and Regular Orthogonal Matrices of Level 2

AU - Abiad, A.

AU - Haemers, W.H.

N1 - Subsequently published in the Electronic Journal of Combinatorics (2012) Pagination: 16

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - cospectral graphs

KW - orthogonal matrices

KW - switching

M3 - Discussion paper

VL - 2012-042

T3 - CentER Discussion Paper

BT - Cospectral Graphs and Regular Orthogonal Matrices of Level 2

PB - Operations research

CY - Tilburg

ER -

Abiad A, Haemers WH. Cospectral Graphs and Regular Orthogonal Matrices of Level 2. Tilburg: Operations research. 2012. (CentER Discussion Paper).