What is degree spectrum in graphs?

557 Views Asked by At

is there any formal definition for degree spectrum? I don't understand it here:

Since trees are a class of graphs, the idea of isomorphism is the same rule as for the general graphs; two trees are isomorphic if and only if they have the same degree spectrum.

1

There are 1 best solutions below

0
On

Did you find your statement here? Here is their definition of degree spectrum

Degree spectrum of tree is the sequence of non-negative integers $\{d_j\}$, where $d_j$ is the number of vertices that have $j$ children.

This is close to the notion of degree sequence. This has nothing to do with the spectrum of a graph (as far as I know, there might be some implications though).

However note that,

  1. Almost all trees are cospectral. You could check this rather old paper. As the number of vertices tends to $\infty$, the fraction of trees for which there exists a cospectral tree goes to 1.
  2. If you restrict yourself to stars (i.e. tree with exactly one vertex of degree higher than 2), then yes, for any two stars, their graph Laplacians have the same spectra, if and only if they are isomorphic.