8
$\begingroup$

The adjacency matrix of a non-oriented connected graph is symmetric, hence its spectrum is real.

If the graph is bipartite, then the spectrum of its adjacency matrix is symmetric about 0. A few lower bounds on the smallest eigenvalue are known in the literature, but I could not find any upper bound. Hence my question: What is known about this? Do there exist graphs whose adjacency matrix is positive semi-definite?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
9
$\begingroup$

Since the eigenvalues are real, and since their sum is the trace of $A$, which is zero, we see that either all eigenvalues are zero, or there are both positive and negative eigenvalues. So no non-empty graph has a positive semidefinite adjacency matrix.

I do not think there is much in the way of upper bounds on the least eigenvalue. For more regular graphs there are bounds on the size of cliques and cocliques that involve the least eigenvalues, and these can be rearranged to get upper bounds on the least eigenvalue. So if $X$ is $k$-regular on $v$ vertices and the max size of a coclique is $a$, then we have an upper bound

$$-\frac{k}{\frac{v}a -1}$$

Here I am just using the Hoffman bound on the size of a coclique.

Improve this answer
$\endgroup$
3
  • $\begingroup$ "So no non-empty graph has a positive semidefinite adjacency matrix." i do not think this is correct. positive semidefinite means that all the eigenvalues are greater or equal to 0. But this is not the case for any non-empty graph. The trace of A is always 0 (no loops considered) thus, there exist negative eigenvalues. $\endgroup$
    – seralouk
    Commented Feb 10, 2019 at 21:07
  • $\begingroup$ @sera: that's what I said. $\endgroup$
    – Chris Godsil
    Commented Feb 10, 2019 at 22:18
  • $\begingroup$ You said : "non-empty graph has a positive semidefinite adjacency matrix" and I think this is not always true $\endgroup$
    – seralouk
    Commented Feb 11, 2019 at 11:28
9
$\begingroup$

A lot is known, see e.g. Andries E. Brouwer, Willem H. Haemers, Spectra of Graphs, but, from some points of view, nothing interesting :) (As usual, this depends on your particular problem.) In some subjects, it is natural to put $-2$ instead of $0$ to the diagonal, shifting the spectrum by $-2$; then, negative definite are Dybkin diagrams and semi-definite are affine Dynkin diagrams. E.g., there seems to be no satisfactory characterization of hyperbolic graphs (with a single positive eigenvalue).

Improve this answer
$\endgroup$
-2
$\begingroup$

Given an Adjacency matrix A on n$\times$n, its Laplacian matrix is defined as: $L=D-A$, where $D$ is the degree matrix and $A$ is the adjacency matrix of the graph. Supose you have a simple graph, then $A$ only contains 1s or 0s and its diagonal elements are all 0s. Therefore the Laplacian matrix is positive definite.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ The question is asking about an upper bound for the smallest eigenvalue of the adjacency matrix. How does your answer address this? $\endgroup$
    – Alex M.
    Commented Sep 27, 2017 at 14:46

You must log in to answer this question.

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