5
$\begingroup$

Is there an effective description of the graphs such that exactly one eigenvalue (of the conventional adjacency matrix) is $>2$ whereas all others are $\le2$?

By "effective" I mean something that would let one iterate through all such graphs with reasonably few (say, a few dozens) vertices, or, better yet, to prove theorems about such graphs :) (Ideally, a list similar to that of Dynkin diagrams.)

The question is motivated by this one: "spectrum of an adjacency matrix" and by my own research. It seems wild, but I'm not an expert.

Improve this question
$\endgroup$
5
  • $\begingroup$ Why are you using "hyperbolic" in the title? (for me, hyperbolic graphs are graphs which are hyperbolic when viewed as metric spaces, which seems irrelevant to your question...) $\endgroup$
    – Alain Valette
    Commented Jan 8, 2014 at 21:52
  • $\begingroup$ Sorry, I don't know the appropriate terminology. They would be (related to) Coxeter schemes of hyperbolic lattices (just like Dynkin diagrams are elliptic and affine Dynkin diagrams are parabolic). But I'm ready to rename if there is an established name for this kind of objects. $\endgroup$
    – Alex Degtyarev
    Commented Jan 8, 2014 at 22:07
  • $\begingroup$ Do you allow the least eigenvalue to be less than $-2$? $\endgroup$
    – Chris Godsil
    Commented Jan 8, 2014 at 23:20
  • $\begingroup$ @Chris Yes, sure. If you put $-2$ instead of $0$ to the main diagonal, the resulting quadratic form must have one positive square and any number of zeroes and/or negative squares. $\endgroup$
    – Alex Degtyarev
    Commented Jan 8, 2014 at 23:23
  • $\begingroup$ @Alex: I was also confused by your title; I'd suggest a more suggestive title such as "Hyperbolic-like spectrum of finite graphs", or so. $\endgroup$
    – YCor
    Commented Jan 9, 2014 at 18:09

2 Answers 2

Reset to default
2
$\begingroup$

I think this question is so hard, since we do not have any control on other eigenvalues, specially on the minimum of them.

As an evidence (and maybe useful for your work), recently S. M. Cioab‎$‎\breve{a}‎$‎, W. H. Haemers, J. Vermette and W. Wong‎ in the paper with name:

"The graphs with all but two eigenvalues equal to ‎‎$‎\mp‎$‎‎ 1",

characterized all graphs that have two eigenvalues $r>1$ and $s<-1$, and all other eigenvalues are $1$ and $-1$. The way of their proof is very interesting and special.

So, if $r>2$ and all other eigenvalues is less than or equal $1$, we have very difficult task to describe these graphs.

Do you have any evidences that hopeful you for solving this problem in general?

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. No, I have no evidence except that the problem is very natural: it is related to geometry. I did mention that the problem appears wild but, once again, I'm not an expert. $\endgroup$
    – Alex Degtyarev
    Commented Jan 9, 2014 at 20:05
1
$\begingroup$

I do not recall seeing such a characterization.

However Neumaier has looked at some related stuff. In A. Neumaier, J. J. Seidel "Discrete hyperbolic geometry" they consider graphs where the second largest eigenvalue is equal to 2. The paper Renee Woo, Arnold Neumaier "On Graphs Whose Spectral Radius is Bounded by 3/\sqrt{2}" might also contain something of interest.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. Alas, they don't really consider them; they rather mention a few special classes and do a bunch of examples. Though, they use a name (reflexive graphs), which I personally do not understand, but I have edited the title :) $\endgroup$
    – Alex Degtyarev
    Commented Jan 9, 2014 at 23:22

You must log in to answer this question.

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