Welcome to MathOverflow

Question

2

I suspect this could be an easy one but I am not an expert in algebraic graph theory.

Let $Q(G)$ define the Laplacian matrix for a simple graph $G$. It is well known that n is an eigenvalue of $Q(K_n)$ with multiplicity $n-1$. I was wondering if graphs $G$ of order $n$ such that $Q(G)$ has an eigenvalue of multiplicity $n-1$ have been characterized.

More specifically, is there any other graph of order $n$ besides $K_n$ such that respective Laplacian matrix has an eigenvalue of multiplicity $n-1$ ?

I think an answer could perhaps be found here https://springerlink3.metapress.com/content/a01321p632887837/resource-secured/?target=fulltext.pdf&sid=rrxkjv553gcfwriiuwfaip55&sh=www.springerlink.com but needless to say I do not have access to the paper.

flag	asked Jul 11 2011 at 20:52 Jernej 952●5●19

Igor Rivin · Accepted Answer · 2011-07-11 21:14:21Z UTC

4

Such a graph has only two distinct eigenvalues, and graphs with few eigenvalues have been studied. See

http://cage.ugent.be/geometry/Theses/30/evandam.pdf

answered Jul 11 2011 at 21:14

Igor Rivin
31.3k●3●37●71

1

Just for completeness I will mention, that the author of the thesis states that the only graph with two distinct eigenvalues is the complete graph. – Jernej Jul 11 2011 at 22:02

Graphs of order n with a Laplacian eigenvalue of multiplicity n-1.

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.