1
$\begingroup$

Let $G= (V,E)$ be a finite, undirected and unweighted graph with $V = \{v_1,\ldots, v_n\}$. Denote by $d_i$ the degree of $v_i$, i.e. the number of vertices that are adjacent to $v_i$. Let $A$ be the adjacency matrix of $G$ and $D = diag(d_1, \ldots d_n)$. Then the Laplacian of $G$ is defined to be $$L = D - A$$ and the normalized Laplacian $$\Delta = I - D^{-1}A$$ (I assume that $d_i \neq 0$ for all $i$). Denote by $\lambda_0 \leq \lambda_1 \leq \ldots \leq \lambda_{n-1}$ the eigenvalues of $\Delta$. Then $\lambda_0 = 0$ and $\lambda_{n-1} \leq 2$.

Most results in spectral graph theory focus on $\lambda_1$ and $\lambda_{n-1}$ as they determine global properties of $G$ very nicely. I'm also familiar with some results that show a connection between $\lambda_k$ and how hard it is to partition $G$ into $k+1$ subgraphs.

However, looking at some examples it seems to me that there should be some characterization of when $\Delta$ has EV $1$. I believe that this is connected to the occurrence of special subgraphs but I'm having a hard time finding papers/literature that deal with that topic. So my question is: Are there papers dealing with characterizing non-extremal eigenvalues of $\Delta$ and especially $\lambda = 1$?

$\endgroup$
4
  • 1
    $\begingroup$ We have $\Delta x=x$ if and only if $Ax=0$. There is no simple combinatorial condition for when $A$ is not invertible. $\endgroup$ Jun 3, 2015 at 13:57
  • $\begingroup$ @RichardStanley When you say that there is no simple combinatorial condition, do you mean that none has been discovered yet or that there exist sufficiently many examples to indicate that $Ax = 0$ occurs in completely independent situations? $\endgroup$ Jun 3, 2015 at 14:11
  • 1
    $\begingroup$ You are asking when a (traceless) symmetric (0,1)-matrix is invertible. This is a question of linear algebra, not combinatorics. $\endgroup$ Jun 3, 2015 at 18:19
  • $\begingroup$ @RichardStanley Obviously you are right that the problem seems to be strongly connected to linear algebra. However, if we are assuming some additional conditions like connectedness of $G$, there might exist a more geometrical interpretation of $\det A = 0$ in terms of the structure of $G$. $\endgroup$ Jun 3, 2015 at 18:26

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.