3
$\begingroup$

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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

  • We could discuss the negative adjacency matrix $-A$ and now the smallest eigenvalue is $-d$ and any partition works.

That seems like a cheap example, however the Laplacian matrix is $L=D-A$ where $D$ is the diagonal matrix of degrees.

  • For any simple graph the eigenvalues of $L$ are real, the smallest is $0$ and the eigenvector is $\mathbf{1}$, so again any partition works.

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.

  • I imagine that there are similar construction/partition pairs which work
Improve this answer
$\endgroup$
5
  • $\begingroup$ Aaron, I'm not sure I understand what you mean by saying that a partition "works". $\endgroup$
    – Felix Goldberg
    Commented May 8, 2012 at 21:54
  • $\begingroup$ I mean that the given partition supports an eigenvector for the chosen eigenvalue. In other words: "the" matrix of the graph (whichever one you chose) has an eigenvector for the chosen eigenvalue with the property that each entry depends only on which class of the partition the corresponding vertex belongs to. $\endgroup$
    – Aaron Meyerowitz
    Commented May 8, 2012 at 22:37
  • $\begingroup$ If I remember correctly (for the adjacency matrix), there is an eigenvector that "works" in this sense exactly unless every eigenvector for that eigenvalue sums to zero in each cell of the partition. $\endgroup$
    – Brendan McKay
    Commented May 9, 2012 at 6:11
  • $\begingroup$ You remember correctly. Suppose that the adjacency matrix $A$ of a graph with $v$ vertices has $d$ eigenvalues and that we have an equitable partition $P$ with $c$ classes of sizes $v_1\cdots v_c$ Then the vectors constant on each class of $P$ form an invariant subspace $T$ under the action of $A$. The projection of a vector onto $T$ assigns the common value $\frac{s_i}{\sqrt{v_i}}$ to the vertices in cell $i$ where $s_i$ is the sum of the entries in that cell. SInce this projection sends an eigenspace into itself (cont.) $\endgroup$
    – Aaron Meyerowitz
    Commented May 10, 2012 at 19:10
  • $\begingroup$ , if some vector in that eigenspace has a non-zero sum over some cell then the projection is a non-zero eigenvector for the appropriate eigenvalue and supported by the partition. At most $c$ of the $d$ eigenvalues can enjoy such an eigenvector. The largest eigenvalue always does. The question was, under what conditions can we be sure that the smallest eigenvalue does? $\endgroup$
    – Aaron Meyerowitz
    Commented May 10, 2012 at 19:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .