It is well known that if $\pi$ is an equitable partition of a graph, then the spectrum of the corresponding partition matrix is a subset of the spectrum of the graph's matrix (where the matrix can be the adjacency, Laplacian, or signless Laplacian – under suitable definitions).
What I'd like to know is whether it is known under which conditions the smallest eigenvalue of the partition matrix is actually the smallest eigenvalue of the graph. One such example that I am aware of is in this paper, where this result is proved for connected threshold graphs:
Tam, Bit-Shun; Wu, Shu-Hui On the reduced signless Laplacian spectrum of a degree maximal graph. (English) [J] Linear Algebra Appl. 432, No. 7, 1734-1756 (2010)
Thanks in advance!
Best Answer
The question is fairly broad. I can say a number of things, but none of them are very deep. For a regular graph the largest eigenvalue of the adjacency matrix, $A$, is the common degree with eigenvector $\mathbf{1}$, the all $1$'s vector. So any partition supports that eigenvector.
That seems like a cheap example, however the Laplacian matrix is $L=D-A$ where $D$ is the diagonal matrix of degrees.
Probably for the Laplacian you would care more about the largest eigenvalue. For the rest of this answer I'll just consider the adjacency matrix of a simple connected graph.
In a distance regular graph of diameter $k$ there are $k+1$ eigenvalues and the partition according to distance from a point supports $k+1$ eigenvectors, one for each eigenvalue, so that partition works.
That is the partition according to distance from a singleton set $S=\lbrace v\rbrace$. The same is true for any partition according to distance from a set $S$ provided that the partition is equitable and there are still $k+1$ parts. There are non-trivial examples of this. Consider a graph based on an $n \times n$ grid with points in the same row or column all adjacent. The diameter is $2$ and remains $2$ if we partition according to distance from an $m \times m$ subgrid (here $m \lt n$). If we use an $m_1 \times m_2$ sub-grid then the same partition supports a full set of eigenvectors. This $3$ class partition is not equitable but can be made so by splitting the middle class into its two connected components. This is a small diameter Hamming graph. Everything remains true (with the obvious changes) for arbitrary Hamming graphs. Something similar happens with Johnson Graphs.
In a regular bipartite graph the smallest eigenvalue is $-d$ with eigenvector $1$ on one half and $-1$ on the other. Any partition (equitable or not) which supports this eigenvector works (of course). Said that way it is trivial but seems less so if we say "partition which respects the bipartition". This automatically happens for a semi-regular bipartite graph. Perhaps also for arbitrary bipartite graphs, I did not check.
Based on a quick scan. it seems that the construction you reference appears to be for the obvious partition of graphs (which can be) built as follows: Start with a base graph, replace each vertex by a complete graph or set of disjoint vertices, for each edge of the base graph, use all possible edges between the corresponding parts of the new graph. So this is more general then saying "For a complete graph" but not so much more general. In that paper it is presented as the partition according to a certain equivalence relation, but for many graphs (even some highly symmetric ones) that would end up the partition into singleton sets.