Spectral graph theory: Difference between revisions

Revision as of 16:20, 6 October 2024

Revision as of 04:06, 21 December 2024

Line 24:

A pair of graphs are said to be cospectral mates if they have the same spectrum, but are non-isomorphic.

The smallest pair of cospectral mates is {''K''_1,4, ''C''₄ ∪ ''K''₁}, comprising the 5-vertex [[star (graph theory)|star]] and the [[graph union]] of the 4-vertex [[cycle (graph theory)|cycle]] and the single-vertex graph,<ref>{{mathworld|CospectralGraphs|Cospectral Graphs}}</ref>. The first example of cospectral graphs aswas reported by Collatz and Sinogowitz<ref>Collatz, L. and Sinogowitz, U. "Spektren endlicher Grafen." Abh. Math. Sem. Univ. Hamburg 21, 63–77, 1957.</ref><ref>{{mathworld|CospectralGraphs|Cospectral Graphs}}</ref> in 1957.

The smallest pair of [[polyhedral graph|polyhedral]] cospectral mates are [[enneahedron|enneahedra]] with eight vertices each.<ref>{{citation|title=Topological twin graphs. Smallest pair of isospectral polyhedral graphs with eight vertices|year=1994|last1=Hosoya|last2=Nagashima|last3=Hyugaji|first1=Haruo|first2=Umpei|first3=Sachiko|author1-link=Haruo Hosoya|journal=Journal of Chemical Information and Modeling|volume=34|issue=2|pages=428–431|doi=10.1021/ci00018a033}}.</ref>