2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\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.