2
$\begingroup$

I am searching for algorithms to estimate the radius of a graph, and I found out that there are papers about the spectral radius of a graph. As far as I know, the radius of a graph is $\min_{v \in V} ecc(v)$ where $ecc(v)$ is the depth of a tree rooted at $v$, and the spectral radius of a graph is the largest eigenvalue of its adjacency matrix. Are these two concepts related in some way?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

No, the two notions are unrelated. To see this, we construct a pair of graphs with the same spectrum, but different radius. Graphs that have the same spectrum are called co-spectral. There exist non-isomorphic graphs that have the same spectrum.

This page shows two co-spectral graphs with different radius: the 4-cycle and point has infinite radius, as it is disconnected, but the co-spectral 4-star has radius 1.

The other way around, two graphs of the same radius with a different spectrum, isn't hard to see either. Simply take two graphs with a different number of nodes and the same radius, their spectra must differ as their adjacency matrices have different size.

The word radius is quite general, so it is no surprise to see it in two unrelated terms.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.