For a given undirected graph, it is known that the signless Laplacian $$Q=D+W$$ is positive semidefinite, where $D$ is the degree matrix and $W$ is the adjacency matrix. In particular, the smallest eigenvalue of $Q$ is zero if and only if there is a bipartite component in the graph.
My questions are:
- Is there is a similar operator that helps to identify if the graph is $k$-partite?
- Is it possible to recognize a $k$-partite graph through the spectrum of the adjacency matrix?
Answers with references are strongly appreciated.
For the second equation, suppose $L$ is an $n\times n$ Latin square. Construct a graph $X(L)$ with the $n^2$ entries of $L$ as its vertices, with two entries adjacent if they are in the same row, in the same column, or contain the same entry. Then $X(L)$ is a $(3n-3)$-regular graph and, in fact it is strongly regular. Now let $L_1$ be the multiplication table of the cyclic group of order four, and let $L_2$ be the multiplication table for the Klein 4-group. Then $X(L_2)$ has chromatic number four, but $X(L_1)$ does not contain an independent set of size four, and so its chromatic number is not four. However all Latin square graphs on $n^2$ vertices have the same spectrum.
Therefore the spectrum does not determine whether a graph is 4-partite. This is all treated in Section 10.4 of "Algebraic Graph Theory" by Royle and somebody.
For the first question, I believe the answer is no, but this cannot be proved and so I cannot offer a reference.