Regularity and the Generalized Adjacency Spectra of Graphs

A.A. Chesnokov, W.H. Haemers

Research output: Working paperDiscussion paperOther research output

271 Downloads (Pure)

Abstract

For every rational number x 2 (0; 1), we construct a pair of graphs one regular and one nonregular with adjacency matrices A1 and A2, having the property that A1-xJ and A2-xJ have the same spectrum (J is the all-ones matrix). This solves a problem of Van Dam and the second author.For some values of x, we have generated the smallest examples (with respect to the number of vertices) by computer.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages6
Volume2005-124
Publication statusPublished - 2005

Publication series

NameCentER Discussion Paper
Volume2005-124

Keywords

  • graphs
  • matrices

Fingerprint Dive into the research topics of 'Regularity and the Generalized Adjacency Spectra of Graphs'. Together they form a unique fingerprint.

  • Cite this

    Chesnokov, A. A., & Haemers, W. H. (2005). Regularity and the Generalized Adjacency Spectra of Graphs. (CentER Discussion Paper; Vol. 2005-124). Operations research.