2

Background

Two graphs are said to be adjacency-cospectral (or more commonly just cospectral) if the spectra of their adjacency matrices is the same. Similarly, two graphs are distance-cospectral if the spectra of their distance matrices is the same. (Since both matrices are symmetric, the spectrum is real.) The spectra of adjacency and distance matrices are invariant under graph isomorphism, and thus can be used to distinguish a pair of non-isomorphic graphs in the case that the graphs are not (adjacency or resp. distance) cospectral. My question asks whether one of the adjacency-matrix spectrum or the distance-matrix spectrum is strictly better than the other at distinguishing non-isomorphic graphs.

Community
  • 1
Ben Mares
  • 431
  • 2
  • 8

1 Answers1

2

Here are explicit examples showing that neither type of cospectrality implies the other.

The Hoffman graph and Tesseract graph are well-known to be adjacency-cospectral. A simple computation of the characteristic polynomials in Mathematica shows that these graphs are not distance-cospectral:

ComparePolynomial[matrixtype_, graphlist_] := 
 Factor@CharacteristicPolynomial[GraphData[#, matrixtype], x] & /@ 
   graphlist // MatrixForm
ComparePolynomial["AdjacencyMatrix", {"HoffmanGraph", 
  "TesseractGraph"}]
ComparePolynomial["DistanceMatrix", {"HoffmanGraph", 
  "TesseractGraph"}]

$$ \textrm{Adjacency:}\quad \begin{align*} \textrm{Hoffman:} & \quad (x-4) (x-2)^4 x^6 (x+2)^4 (x+4)\\ \textrm{Tesseract:} & \quad (x-4) (x-2)^4 x^6 (x+2)^4 (x+4) \end{align*} $$ $$ \textrm{Distance:}\quad \begin{align*} \textrm{Hoffman:} & \quad x^3 (x+2)^3 (x^2- 30 x -32 ) (x^2+ 6 x-8 )^4\\ \textrm{Tesseract:} & \quad (x-32) x^{11} (x+8)^4 \end{align*} $$

In the other direction, Heysse constructs a pair of 10-vertex distance-cospectral graphs $G$ and $H$ which are similarly verified not to be adjacency-cospectral:

DistToAdj[list_] := DistToAdj /@ list;
DistToAdj[1] := 1;
DistToAdj[n_Integer] := 0; DG = 
 Partition[{0, 1, 1, 1, 2, 1, 2, 2, 2, 2, 1, 0, 2, 2, 3, 1, 3, 1, 2, 
   3, 1, 2, 0, 1, 1, 2, 1, 3, 3, 1, 1, 2, 1, 0, 1, 1, 1, 2, 2, 2, 2, 
   3, 1, 1, 0, 2, 2, 3, 3, 1, 1, 1, 2, 1, 2, 0, 2, 1, 1, 3, 2, 3, 1, 
   1, 2, 2, 0, 3, 3, 1, 2, 1, 3, 2, 3, 1, 3, 0, 2, 4, 2, 2, 3, 2, 3, 
   1, 3, 2, 0, 4, 2, 3, 1, 2, 1, 3, 1, 4, 4, 0}, 10];
DH = Partition[{
    0, 1, 1, 1, 2, 1, 2, 2, 2, 2, 1, 0, 2, 2, 3, 1, 3, 1, 2, 3, 1, 2, 
    0, 1, 1, 1, 1, 3, 2, 1, 1, 2, 1, 0, 2, 2, 2, 2, 1, 2, 2, 3, 1, 2, 
    0, 2, 2, 4, 3, 1, 1, 1, 1, 2, 2, 0, 2, 2, 1, 2, 2, 3, 1, 2, 2, 2, 
    0, 4, 3, 1, 2, 1, 3, 2, 4, 2, 4, 0, 1, 4, 2, 2, 2, 1, 3, 1, 3, 1, 
    0, 3, 2, 3, 1, 2, 1, 2, 1, 4, 3, 0}, 10];
CharacteristicPolynomial[DistToAdj[#], x] & /@ {DG, DH} // Factor
CharacteristicPolynomial[#, x] & /@ {DG, DH} // Factor

$$ \textrm{Adjacency:}\quad \begin{align*} \textrm{G:} & \quad (4 - x - 44 x^2 - x^3 + 104 x^4 + 67 x^5 - 16 x^6 - 17 x^7 + x^9)x\\ \textrm{H:} & \quad (8 + 27 x - 52 x^2 - 70 x^3 + 58 x^4 + 66 x^5 - 10 x^6 - 16 x^7 + x^9)x \end{align*} $$ $$ \textrm{Distance:}\quad \begin{align*} \textrm{G:} & \quad (2 + x) (40 + 184 x - 190 x^2 - 2237 x^3 - 4322 x^4 - 3512 x^5 - 1320 x^6 - 199 x^7 - 2 x^8 + x^9)\\ \textrm{H:} & \quad (2 + x) (40 + 184 x - 190 x^2 - 2237 x^3 - 4322 x^4 - 3512 x^5 - 1320 x^6 - 199 x^7 - 2 x^8 + x^9) \end{align*} $$

[1] Heysse, Kristin, A construction of distance cospectral graphs, Linear Algebra Appl. 535, 195-212 (2017). ZBL1371.05163. arxiv:1606.06782.

Ben Mares
  • 431
  • 2
  • 8