2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ The link to springerlink.com is broken. I'm also unable to find any copy saved on the Wayback Machine. $\endgroup$
    – The Amplitwist
    Commented Apr 17, 2023 at 5:38

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jernej
    Commented Jul 11, 2011 at 22:02

You must log in to answer this question.

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