4
$\begingroup$

I know that the largest eigenvalue of a graph is bounded between the minimal and maximal row sum of the matrix. If I have a $0-1$ symetric matrix (an adjacency matrix) and I know $k$ of the rows have at least $k$ zeros in them (more specifically, I know $k$ is the maximum size of an all zeros principal sub-matrix of the adjacency matrix), is there anything else I can tell about the largest eigenvalue (or others eigenvalues)?

Is there anything I can tell about the eigenvalues which implies I have that kind of principal sub-matrix?

Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

You are asking for relationships between the maximum independent set and the eigenvalues. If you search with those terms you will find several. For example, Haemers proved that the maximum size of an independent set is bounded above by $$ n\frac{-\lambda_1\lambda_n}{\delta^2-\lambda_1\lambda_n},$$ where $\lambda_1,\lambda_n$ are the largest and smallest eigenvalues and $\delta$ is the minimum degree.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! Do you know the name of the article? $\endgroup$
    – Yahav Boneh
    Commented Apr 20, 2020 at 11:30

You must log in to answer this question.

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