I am looking for a graph for which $2 d_{i} < \mu_{i}$, for some index $i$, where $\mu_{1} \leq \mu_{2} \leq \dots\leq \mu_{n}$ are the eigenvalues of the Laplacian matrix $L(G)$ and $d_{1} \leq d_{2} \leq \dots \leq d_{n}$ are the node degrees.

According to the literature and existing upper/lower bounds on the eigenvalues of the Laplacian as a function of node degrees, it seems there is a graph with this property. However, I was not able to find such a graph by generating all graph with $4, 5, \dots, 10$ vertices. Any help or advice for a possible hypothesis confirmation or rejection would be appreciated.

Related references:

  • 2
    $\begingroup$ There is no example of such graphs. For this, you can use min-max theorem and the restriction to the subspace generated by vectors supported in first $i$ vertices of the graph. $\endgroup$ – Mostafa Apr 9 '18 at 14:21

This is an expanded solution based on the comment of @mostafa.

Such graphs dose not exist.

Let $L$ be the Laplacian of the graph. Suppose that diagonal elements of $L$ are sorted sequence of degrees $d_1\leq \ldots \leq d_n$. By Min-Max theorem, we have

$$\mu_i= \min_{U<\mathbb R^n,\dim(U)=i} \big\{ \max_{x \in U, \|x\|=1} x^TL x \big\} $$

So, if there exists an $i$-dimensional subspace of $\mathbb R^n$, say $U$, such that

$$ \max_{x \in U, \|x\|=1} x^TL x \leq 2d_i $$ then we have $\mu_i \leq 2d_i$.

Let $U := \langle e_1,\ldots,e_i\rangle$, where $e_k$ is $k$-th element of the standard base of $\mathbb R^n$, for $k=1,\ldots,i$. Suppose that $x\in U$ and $\|x\|=1$. Note that only first $i$ elements of $x$ are nonzero. we have $$ x^TL x = \sum_{ab \in E(G),a<b} (x_a-x_b)^2 \leq \sum_{ab \in E(G),a<b} 2(x_a^2+x_b^2)=2\sum_{k=1}^id_k x_k^2\leq2d_i. $$ Now the statment at hand.


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.