Return to Question

Let G be an undirected graph with the node set $V$ and the Laplacian matrix $L$. Let $N(v)$ denote the neighbors of a node $v$ and $|N(v)|$ its degree. Then a partition $\pi=(V_1, V_2, \ldots, V_k)$ is almost equitable if it holds that $\forall i \ne j\in\{1,\ldots,k\}$ $\forall v, u\in V_i$ $|N(v)\cap V_j|=|N(u)\cap V_j|$, i. e. that the number of neighbors of a node $v$ in $V_i$ in a different component $V_j$ does not depend on the choice of $v$.

It is known that if $\pi$ is an almost equitable partition of $L$, then (after reordering the vertices appropriately) $L$ has an eigenvector of the form $x=(x_1,x_2,\ldots,x_k)^T$, where $x_i\in {\mathbb{R}}^{|V_i|}$ and $x_i=c_i\mathbf{1}$, $c_i\in \mathbb{R}$.

I had previously asked whether the converse was also true. The converse is not true. For example, the graph with the Laplacian $\begin{pmatrix} 2 & -1 & -1 & 0 & 0 & 0\\\ -1 & 3 & -1 & -1 & 0 & 0\\\ -1 & -1 & 3 & -1 & 0 & 0\\\ 0 & -1 & -1 & 4 & -1 & -1\\\ 0 & 0 & 0 & -1 & 1 & 0\\ 0 & 0 & 0 & -1 & 0 & 1\end{pmatrix}$ has an eigenvector $x=(c_1, c_2, c_2, c_2, c_3, c_3)^T$, which does not correspond with an almost equitable partition. However, if you consider the graph structure, you see that each node in a component $V_i$ has either the same amount of edges to a component $V_j$ or no edges to $V_j$. Just from looking at examples, it seems to always be the case if an eigenvector with repeated entries is present in the graph. However, so far, I have not been able to prove this.

Are there any results about this in the literature? Alas I am not very familiar with algebraic graph theory, but all the literature I could find on Laplacian eigenvectors either did not relate the eigenvector to the graph structure (apart from the Perron ev), or only studied graphs that allowed almost equitable partitions.

Are there necessary and sufficient conditions on the graph structure, such that the graph Laplacian does not have eigenvectors of the form $x$ (apart from $\mathbf{1}$)?

Let G be an undirected graph with the node set $V$ and the Laplacian matrix $L$. Let $N(v)$ denote the neighbors of a node $v$ and $|N(v)|$ its degree. Then a partition $\pi=(V_1, V_2, \ldots, V_k)$ is almost equitable if it holds that $\forall i \ne j\in\{1,\ldots,k\}$ $\forall v, u\in V_i$ $|N(v)\cap V_j|=|N(u)\cap V_j|$, i. e. that the number of neighbors of a node $v$ in $V_i$ in a different component $V_j$ does not depend on the choice of $v$.

It is known that if $\pi$ is an almost equitable partition of $L$, then (after reordering the vertices appropriately) $L$ has an eigenvector of the form $x=(x_1,x_2,\ldots,x_k)^T$, where $x_i\in {\mathbb{R}}^{|V_i|}$ and $x_i=c_i\mathbf{1}$, $c_i\in \mathbb{R}$.

I had previously asked whether the converse was also true. The converse is not true. For example, the graph with the Laplacian $\begin{pmatrix} 2 & -1 & -1 & 0 & 0 & 0\\\ -1 & 3 & -1 & -1 & 0 & 0\\\ -1 & -1 & 3 & -1 & 0 & 0\\\ 0 & -1 & -1 & 4 & -1 & -1\\\ 0 & 0 & 0 & -1 & 1 & 0\\ 0 & 0 & 0 & -1 & 0 & 1\end{pmatrix}$ has an eigenvector $x=(c_1, c_2, c_2, c_2, c_3, c_3)^T$, which does not correspond with an almost equitable partition. However, if you consider the graph structure, you see that each node in a component $V_i$ has either the same amount of edges to a component $V_j$ or no edges to $V_j$. Just from looking at examples, it seems to always be the case if an eigenvector with repeated entries is present in the graph. However, so far, I have not been able to prove this.

Are there any results about this in the literature? Alas I am not very familiar with algebraic graph theory, but all the literature I could find on Laplacian eigenvectors either did not relate the eigenvector to the graph structure (apart from the Perron ev), or only studied graphs that allowed almost equitable partitions.

Are there necessary and sufficient conditions on the graph structure, such that the graph Laplacian does not have eigenvectors of the form $x$ (apart from $\mathbf{1}$)?

My original question has led to a different one. I have edited my original question, hoping that this is the right way to proceed?

Let G be an undirected graph with the node set $V$ and the Laplacian matrix $L$. Let $N(v)$ denote the neighbors of a node $v$ and $|N(v)|$ its degree. Then a partition $\pi=(V_1, V_2, \ldots, V_k)$ is almost equitable if it holds that $\forall i \ne j\in\{1,\ldots,k\}$ $\forall v, u\in V_i$ $|N(v)\cap V_j|=|N(u)\cap V_j|$, i. e. that the number of neighbors of a node $v$ in $V_i$ in a different component $V_j$ does not depend on the choice of $v$.

It is known that if $\pi$ is an almost equitable partition of $L$, then (after reordering the vertices appropriately) $L$ has an eigenvector of the form $x^T=(x_1^T,x_2^T,\ldots,x_k^T)^T$, where $x_i\in {\mathbb{R}}^{|V_i|}$ and $x_i=c_i\mathbf{1}$, $c_i\in \mathbb{R}$.

I had previously asked whether the converse was also true. The converse is not true. For example, the graph with the Laplacian $\begin{pmatrix} 2 & -1 & -1 & 0 & 0 & 0\\\ -1 & 3 & -1 & -1 & 0 & 0\\\ -1 & -1 & 3 & -1 & 0 & 0\\\ 0 & -1 & -1 & 4 & -1 & -1\\\ 0 & 0 & 0 & -1 & 1 & 0\\ 0 & 0 & 0 & -1 & 0 & 1\end{pmatrix}$ has an eigenvector $x=(c_1, c_2, c_2, c_2, c_3, c_3)^T$, which does not correspond with an almost equitable partition. However, if you consider the graph structure, you see that each node in a component $V_i$ has either the same amount of edges to a component $V_j$ or no edges to $V_j$. Just from looking at examples, it seems to always be the case if an eigenvector with repeated entries is present in the graph. However, so far, I have not been able to prove this.

Are there any results on this in the literature? Alas I am not very familiar with algebraic graph theory, but all the literature I could find on Laplacian eigenvectors either did not relate the eigenvector to the graph structure (apart from the Perron ev), or only studied graphs that allowed almost equitable partitions.

Are there necessary and sufficient conditions on the graph structure, such that the graph Laplacian does not have eigenvectors of the form $x$ (apart from $\mathbf{1}$)?

Let G be an undirected graph with the node set $V$ and the Laplacian matrix $L$. Let $N(v)$ denote the neighbors of a node $v$ and $|N(v)|$ its degree. Then a partition $\pi=(V_1, V_2, \ldots, V_k)$ is almost equitable if it holds that $\forall i \ne j\in\{1,\ldots,k\}$ $\forall v, u\in V_i$ $|N(v)\cap V_j|=|N(u)\cap V_j|$, i. e. that the number of neighbors of a node $v$ in $V_i$ in a different component $V_j$ does not depend on the choice of $v$.

It is known that if $\pi$ is an almost equitable partition of $L$, then (after reordering the vertices appropriately) $L$ has an eigenvector of the form $x=(x_1,x_2,\ldots,x_k)^T$, where $x_i\in {\mathbb{R}}^{|V_i|}$ and $x_i=c_i\mathbf{1}$, $c_i\in \mathbb{R}$.

I had previously asked whether the converse was also true. The converse is not true. For example, the graph with the Laplacian $\begin{pmatrix} 2 & -1 & -1 & 0 & 0 & 0\\\ -1 & 3 & -1 & -1 & 0 & 0\\\ -1 & -1 & 3 & -1 & 0 & 0\\\ 0 & -1 & -1 & 4 & -1 & -1\\\ 0 & 0 & 0 & -1 & 1 & 0\\ 0 & 0 & 0 & -1 & 0 & 1\end{pmatrix}$ has an eigenvector $x=(c_1, c_2, c_2, c_2, c_3, c_3)^T$, which does not correspond with an almost equitable partition. However, if you consider the graph structure, you see that each node in a component $V_i$ has either the same amount of edges to a component $V_j$ or no edges to $V_j$. Just from looking at examples, it seems to always be the case if an eigenvector with repeated entries is present in the graph. However, so far, I have not been able to prove this.

Are there any results about this in the literature? Alas I am not very familiar with algebraic graph theory, but all the literature I could find on Laplacian eigenvectors either did not relate the eigenvector to the graph structure (apart from the Perron ev), or only studied graphs that allowed almost equitable partitions.

Are there necessary and sufficient conditions on the graph structure, such that the graph Laplacian does not have eigenvectors of the form $x$ (apart from $\mathbf{1}$)?

Let G be an undirected graph with the node set $V$ and the Laplacian matrix $L$. Let $N(v)$ denote the neighbors of a node $v$ and $|N(v)|$ its degree. Then a partition $\pi=(V_1, V_2, \ldots, V_k)$ is almost equitable if it holds that $\forall i \ne j\in\{1,\ldots,k\}$ $\forall v, u\in V_i$ $|N(v)\cap V_j|=|N(u)\cap V_j|$, i. e. that the number of neighbors of a node $v$ in $V_i$ in a different component $V_j$ does not depend on the choice of $v$.

It is known that if $\pi$ is an almost equitable partition of $L$, then (after reordering the vertices appropriately) $L$ has an eigenvector of the form $x^T=(x_1^T,x_2^T,\ldots,x_k^T)^T$, where $x_i\in {\mathbb{R}}^{|V_i|}$ and $x_i=c_i\mathbf{1}$, $c_i\in \mathbb{R}$.

I had previously asked if the converse was also true. The converse is not true. For example, the graph with the Laplacian $\begin{pmatrix} 2 & -1 & -1 & 0 & 0 & 0\\\ -1 & 3 & -1 & -1 & 0 & 0\\\ -1 & -1 & 3 & -1 & 0 & 0\\\ 0 & -1 & -1 & 4 & -1 & -1\\\ 0 & 0 & 0 & -1 & 1 & 0\\\0 & 0 & 0 & -1 & 0 & 1\end{pmatrix}$ has an eigenvector $x=(c_1, c_2, c_2, c_2, c_3, c_3)^T$, which does not correspond with an almost equitable partition. However, if you consider the graph structure, you see that each node in a component $V_i$ has either the same amount of edges to a component $V_j$ or no edges to $V_j$. Just from looking at examples, it seems to always be the case if an eigenvector with repeated entries is present in the graph. However, so far, I have not been able to prove this.

Are there any results on this in the literature? Alas I am not very familiar with algebraic graph theory, but all the literature I could find on Laplacian eigenvectors either did not relate the eigenvector to the graph structure (apart from the Perron ev), or only studied graphs that allowed almost equitable partitions.

Are there necessary and sufficient conditions on the graph structure, such that the graph Laplacian does not have eigenvectors of the form $x$ (apart from $\mathbf{1}$)?

Let G be an undirected graph with the node set $V$ and the Laplacian matrix $L$. Let $N(v)$ denote the neighbors of a node $v$ and $|N(v)|$ its degree. Then a partition $\pi=(V_1, V_2, \ldots, V_k)$ is almost equitable if it holds that $\forall i \ne j\in\{1,\ldots,k\}$ $\forall v, u\in V_i$ $|N(v)\cap V_j|=|N(u)\cap V_j|$, i. e. that the number of neighbors of a node $v$ in $V_i$ in a different component $V_j$ does not depend on the choice of $v$.

It is known that if $\pi$ is an almost equitable partition of $L$, then (after reordering the vertices appropriately) $L$ has an eigenvector of the form $x^T=(x_1^T,x_2^T,\ldots,x_k^T)^T$, where $x_i\in {\mathbb{R}}^{|V_i|}$ and $x_i=c_i\mathbf{1}$, $c_i\in \mathbb{R}$.

I had previously asked whether the converse was also true. The converse is not true. For example, the graph with the Laplacian $\begin{pmatrix} 2 & -1 & -1 & 0 & 0 & 0\\\ -1 & 3 & -1 & -1 & 0 & 0\\\ -1 & -1 & 3 & -1 & 0 & 0\\\ 0 & -1 & -1 & 4 & -1 & -1\\\ 0 & 0 & 0 & -1 & 1 & 0\\ 0 & 0 & 0 & -1 & 0 & 1\end{pmatrix}$ has an eigenvector $x=(c_1, c_2, c_2, c_2, c_3, c_3)^T$, which does not correspond with an almost equitable partition. However, if you consider the graph structure, you see that each node in a component $V_i$ has either the same amount of edges to a component $V_j$ or no edges to $V_j$. Just from looking at examples, it seems to always be the case if an eigenvector with repeated entries is present in the graph. However, so far, I have not been able to prove this.

Are there any results on this in the literature? Alas I am not very familiar with algebraic graph theory, but all the literature I could find on Laplacian eigenvectors either did not relate the eigenvector to the graph structure (apart from the Perron ev), or only studied graphs that allowed almost equitable partitions.

Are there necessary and sufficient conditions on the graph structure, such that the graph Laplacian does not have eigenvectors of the form $x$ (apart from $\mathbf{1}$)?