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.

$\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$ Jan 8 '14 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$ Jan 8 '14 at 22:07
  • $\begingroup$ Do you allow the least eigenvalue to be less than $-2$? $\endgroup$ Jan 8 '14 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$ Jan 8 '14 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
    Jan 9 '14 at 18:09
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?

$\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$ Jan 9 '14 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.

$\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$ Jan 9 '14 at 23:22

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.