1
$\begingroup$

If a graph $G$ has an equitable partition, then its charachteristic polynomial (for the adjacency matrix) has a divisor that can be seen as the characteristic polynomial (for the adjacency matrix) of a oriented and weighted, but smaller, graph $G'$. In other words, the spectrum of $G$ contains the spectrum of $G'$. Equality (without counting multiplicity) holds if the graph has further properties, in particular if it is walk regular (an old result by Godsil and McKay).

If $G$ only has an almost equitable partition, then the above assertion still holds if we replace "adjacency matrix" by "discrete laplacian". Is it known whether equality of spectra holds in special cases?

$\endgroup$
1
$\begingroup$

I think the real problem is that the obvious notion of ``Laplacian walk-regular'' implies that the graph must be regular.

The proof of the ``old result'' can be modified to yield the following. Let $L$ be the Laplacian of the graph $X$, let $v$ be a vertex in $X$ and let $L_v$ denote the matrix we get by deleting the $v$-row and $v$-column from $L$. (So $L_v$ is not a Laplacian.) Assume that if $\lambda$ is an eigenvalue of $L$ with multiplicity $m\ge1$, then the multiplicity of $\lambda$ as an eigenvalue of $L_v$ is $m-1$ (the least it can be). If $\pi$ is an almost equitable partition of $X$ in which $\{v\}$ is a cell, then each eigenvalue of $L$ occurs as an eigenvalue of $L_v$.

This condition implies the old result, but I think it would be difficult to apply in practice.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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