Graph Spectrum

Author

Eric W. Weisstein
March 15, 2017

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/GraphSpectrum.nb.

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

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

Two Graphs with the Same spectrum

ShowGraphArray[CircularEmbedding/@{g1,g2},
VertexStyle->Disk[.05],
VertexColor->Red,
GraphicsSpacing->.7]

Spectrum/@{g1=GraphUnion[Cycle[4],CompleteGraph[1]],g2=Star[5]}

Spectrum/@{g1=GraphUnion[Cycle[4],CompleteGraph[1]],g2=Star[5]}

IsomorphicQ[g1,g2]

Named Graphs

up[s_String]:=Module[{c=Characters[s]},
(c[[#]]=ToUpperCase[c[[#]]])&/@(Prepend[Flatten[Position[c," "]],0]+1);
StringJoin@@DeleteCases[c," "]
]

Print[{#,TimeConstrained[Spectrum[ToExpression[#]]//SpectrumForm//TraditionalForm//Timing,10]}]&/@Sort[Flatten[{"PappusGraph","DesarguesGraph","HeawoodGraph","PetersenGraph","CoxeterGraph","ChvatalGraph","FruchtGraph","FolkmanGraph","FranklinGraph","GrayGraph","GrotztschGraph","HerschelGraph","LeviGraph","McGeeGraph","MeredithGraph","RobertsonGraph","ThomassenGraph","TutteGraph","WaltherGraph","ClebschGraph","BiggsSmithGraph","DoyleGraph","DyckGraph","HoffmanGraph","HoffmanSingletonGraph","MeringerGraph","MoebiusKantorGraph","RobertsonWegnerGraph","UtilityGraph","WongGraph","FosterGraph",
up/@PlatonicGraphName/@Range[5],
up/@ArchimedeanGraphName/@Range[13]
}]];

Missing

GraphData["Spectrum","Missing"]

Check

Monitor[DeleteCases[{g=#,Spectrum[Graph[#]],Eigenvalues[AdjacencyMatrix[GraphData[#]]]}&/@GraphData[;;10],{_,x_,x_}],g]//Timing

Monitor[DeleteCases[{g=#,Spectrum[Graph[#]],Eigenvalues[AdjacencyMatrix[GraphData[#]]]}&/@GraphData[;;20],{_,x_,x_}],g]//Timing