Cospectral Graphs

Author

Eric W. Weisstein
July 14, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/CospectralGraphs.nb.

For more information, see Eric's MathWorld entry https://mathworld.wolfram.com/CospectralGraphs.html.

©2026 Wolfram Research, Inc. except for portions noted otherwise

Examples

Skiena

Cospectral5=GraphData["NotDeterminedBySpectrum",5]

GraphicsRow[
graphic1=StyleGraphs@Annotate[GraphData[#],PlotLabel->Column[{GraphData[#,"Notation"]/.(s_String/;(StringMatchQ[s,LetterCharacter]):>Style[s,Italic]),GraphData[#,"Spectrum"]//SpectrumForm//TraditionalForm},Alignment->Center]]&/@Cospectral5,
Dividers->All,Alignment->Top,BaseStyle->InsetBoxOptions->{BaseStyle->Directive[LightDarkSwitched@Black,18,FontFamily->"Times",AutoMultiplicationSymbol->None]},ImageSize->500]

van Dam and Haemers 2003

van Dam, E.R. and Haemers, W.~H.  "Which Graphs Are Determined by Their Spectrum?"  Lin. Algebra Appl. 373, 139–162, 2003.  https://doi.org/10.1016/S0024-3795(03)00483-X

v1={{0,0},{1/2,0},{1,0},{1/4,1/3},{3/4,1/3},{1/4,2/3},{3/4,2/3},{0,1},{1/2,1},{1,1}};
e1={e[1,2,3,10,9,8,1,5,2,4,3,7,10,5,7,9,6,8,4,6,1]};
g1=Graph[Range@Length@v1,UndirectedEdge@@@e1,VertexCoordinates->v1,VertexLabels->Automatic]

v2={{0,0},{1/2,0},{1,0},{1/4,1/3},{3/4,1/3},{1/4,2/3},{3/4,2/3},{0,1},{1/2,1},{1,1}};
e2={e[1,2,3,10,9,8,1],e[5,2,4],e[3,7,10],e[5,7,9,6,8],e[4,6,1,4,10],e[3,5,8]};
g2=Graph[Range@Length@v2,UndirectedEdge@@@e2,VertexCoordinates->v2,VertexLabels->Automatic]

CospectralRegular10=RecognizeGraph/@Join[{g1,g2},GraphComplement/@{g1,g2}]

GraphData[#,"CospectralGraphs"]&/@CospectralRegular10

eig=Flatten[GraphData[#,"Spectrum"]&/@CospectralRegular10]//Union

rules=Thread[eig->(eig/.{-1-(Sqrt[5])->Subscript[θ,3],-1+(Sqrt[5])->Subscript[θ,4],(1/2) (-1-(Sqrt[17]))->Subscript[θ,1],(1/2) (-1+(Sqrt[17]))->Subscript[θ,2]})]

GraphicsGrid[
graphic2=Partition[StyleGraphs@Annotate[GraphData[#],PlotLabel->Column[{GraphData[#,"Name"],SpectrumForm[GraphData[#,"Spectrum"]/.rules]},Alignment->Center]]&/@CospectralRegular10,2],
Dividers->All,Alignment->Top,BaseStyle->InsetBoxOptions->{BaseStyle->Directive[LightDarkSwitched@Black,12,FontFamily->"Times",AutoMultiplicationSymbol->None]},ImageSize->500]

Figure

GraphicsGrid[
Transpose[Prepend[graphic2,graphic1]],Dividers->{Thick,{Thick,{True},Thick}},
BaseStyle->InsetBoxOptions->{BaseStyle->Directive[LightDarkSwitched@Black,14,FontFamily->"Times",AutoMultiplicationSymbol->None]}
]

Systematic enumeration

GraphData

AvalableVertexCount[gns_]:=Module[{n},
SelectFirst[gns,IntegerQ[n=Quiet@GraphData[#,"VertexCount"]]&];
n
]

AvalableVertexCount[{{8,56} ,{"Cycle",6}}]

cosp=SortBy[
Union[Sort[Append[GraphData[#,"CospectralGraphNames"],#]]&/@Select[GraphData[All],GraphData[#,"CospectralGraphNames"]=!={}&]],
AvalableVertexCount
];//Timing

TextGrid[Take[Prepend[#,AvalableVertexCount[#]]&/@cosp,20],Dividers->All]

TextGrid[Take[Prepend[#,AvalableVertexCount[#]]&/@Select[cosp,Length[#]==3&],20],Dividers->All]

TextGrid[Take[Prepend[#,AvalableVertexCount[#]]&/@Select[cosp,Length[#]==4&],UpTo@20],Dividers->All]

3 nodes

GraphData["NotDeterminedBySpectrum",3]

IsospectralGraphs[3]

4 nodes

GraphData["NotDeterminedBySpectrum",4]

GraphData[%[[1]],"CospectralGraphNames"]

IsospectralGraphs[4]

5 nodes

GraphData["NotDeterminedBySpectrum",5]

iso5=GroupedIsospectralGraphs[5]

Count[Length/@IsospectralGraphs[5],#]&/@Range[5]

6 nodes

GraphData["NotDeterminedBySpectrum",6]

iso6=IsospectralGraphs[6];//Timing

Count[Length/@iso6,#]&/@Range[10]

%.Range[10]

Last/@iso6

ShowGraphArray[Transpose[Last/@Join[iso5,iso6]]]

7 nodes

iso7=IsospectralGraphs[7];//Timing

Count[Length/@iso7,#]&/@Range[10]

%.Range[10]

ShowGraphArray[Transpose[Last/@Select[iso7,Length[Last[#]]==3&]]]

8 nodes

iso8=IsospectralGraphs[8];//Timing

Count[Length/@iso8,#]&/@Range[10]

%.Range[10]

9 nodes

iso9=IsospectralGraphs[9];//Timing

Count[Length/@iso9,#]&/@Range[15]

%.Range[15]

Flatten[iso9,1]//Length

Compute 1-10 nodes

DateString[]

Compute

$GraphData10Nodes=GraphData[;;10];

(valid[#]=True)&/@$GraphData10Nodes;
valid[_]=False;

$GraphDataIndexRules=Association[(Cases[GraphData[#,"StandardNames"],{_Integer,_Integer}][[1]]->#)&/@$GraphData10Nodes];

ComputeCharacteristic[n_]:=Module[
(* Import[...,"Lines"] takes > 50 GB on a 5 GB file, so use ReadList[..., String] *)
{groups={n,#}&/@#[[All,2]]&/@Select[SplitBy[Sort[MapIndexed[{#,#2[[1]]}&,Hash/@ReadList[FileNameJoin[{$GraphDataDirectory,"Nodes","CharacteristicPolynomial","CharacteristicPolynomial_"<>If[n<10,"0",""]<>ToString[n]<>".m"}],String]]],First],Length[#]>1&],
c,
indexedgroups,
definedindexedgroups
},
indexedgroups=(groups/.$GraphDataIndexRules);
definedindexedgroups=Pick[indexedgroups,valid/@Or@@#&/@indexedgroups];
Flatten[((First[#]->SortBy[Rest[#],First[Flatten[{#}]]&])&/@Pick[c=NestList[RotateRight,#,Length[#]-1],valid/@c[[All,1]]])&/@definedindexedgroups]
]

ComputeCharacteristic[5]

(cospec=Join@@Monitor[Table[ComputeCharacteristic[n],{n,10}],n])//Length//Timing

Sort[cospec[[All,1]]]

CospectralGraphNames

l={#1,{0,#3}}&@@@DeleteCases[{#1,GraphData[#1,"CospectralGraphNames"],#2}&@@@cospec,{_,x_,x_}]

PropertyReplace[l,"CospectralGraphNames","15.1"]

RenameGraphFiles[]

DeterminedBySpectrum === True

l2={#,{0,True}}&/@Select[Complement[GraphData[;;10],cospec[[All,1]]],GraphData[#,"DeterminedBySpectrum"]=!=True&]

MissingFillin[l2,"DeterminedBySpectrum"]

RenameGraphFiles[]

DeterminedBySpectrum === False

l3={#,{0,False}}&/@Select[cospec[[All,1]],GraphData[#,"DeterminedBySpectrum"]=!=False&]

MissingFillin[l3,"DeterminedBySpectrum"]

RenameGraphFiles[]

Compute >10 nodes

DateString[]

Compute

groups=SplitBy[Sort[{
Sort[{poly=Expand[GraphData[#,"CharacteristicPolynomial"][x]],-poly}][[1]],
#
}&/@Intersection[GraphData[11;;],GraphData["CharacteristicPolynomial","Defined"]]],First];//Timing

cospec=Pick[groups,Length/@groups,Except[1,_Integer]][[All,All,2]]

CospectralGraphNames

new=DeleteCases[
{First[#],GraphData[#[[1]],"CospectralGraphNames"],SortBy[Rest[#],First[Flatten[{#}]]&]}&/@Flatten[NestList[RotateRight,#,Length[#]-1]&/@cospec,1],
{_,x_,x_}]

l={#1,{0,#3}}&@@@new

PropertyReplace[l,"CospectralGraphNames","15.1"]

RenameGraphFiles[]

DeterminedBySpectrum

l2={#,{0,False}}&/@Select[Flatten[cospec,1],GraphData[#,"DeterminedBySpectrum"]=!=False&]

MissingFillin[l2,"DeterminedBySpectrum"]

RenameGraphFiles[]

GraphData

GraphDataClassString

GraphDataClassString["NotDeterminedBySpectrum"]