show/hide this revision's text 3 added 187 characters in body

I am going to call the partitions you describe simply equitable (am I missing something?) Here is a graph labelled according to an eigenvector. The red nodes are $+1$ the green are $-1$ and the black are $0$ the corresponding partition is not equitable. The second graph is about the same but seems more clearly a counterexample to your revised question.

alt text alt text

Here is what I think is true: A partition with $k$ parts is equitable iff it supports $k$ linearily independent eigenvectors (for the adjacency matrix $A$ or the Laplacian matrix $L$). Here is a rough sketch of a proof for the case of $A$ (which looks ok to me, but check for yourself) .

Consider a graph and a partition of the $n$ vertices into $k$ classes. The characteristic vectors of the classes are $k$ $0-1$ vectors $v_1,v_2,\dots,v_k$ with sum the all $1$'s vector. They span a dimension $k$ subspace $V$ of $\mathbb{R}^n.$

The partition is defined to be equitable if there are $k^2$ constants $c_{ij}$ such that $Av_j=\sum c_{ij}v_i.$ Mure succinctly: if $AV=V.$ Note that $n_ic_{ij}=n_jc_{ji}.$ Thus(?) $\mathbb{R}^k$ has a basis of eigenvectors for the matrix $C=\left(c_{ij}\right)$ . These lift to $k$ vectors in $\mathbb{R}^n$ which are eigenvectors for $A$ and a basis for $V.$

Conversely, if $V$ has a basis which are eigenvectors of $A$ then it follows that $AV=V.$

old answer left to explain comments:

No. A path with 5 vertices has eigenvector $[1,1,0,-1,-1]$ but the partition is not almost equitable.

More generally, take two graphs $G_1$ and $G_3$ both regular of degree $d$. In addition take an arbitrary graph $G_2$ and connect each vertex of $u \in G_2$ to $s\alpha_u$ vertices of $G_1$ and $t\alpha_u$ vertices of $G_3$ where $\alpha_u$ can depend on $u$. Then this partition of $G=G_1 \cup G_2 \cup G_3$ supports an eigenvector (for $d$) with values $t,0$ and $-s$ respectively on $G_1,G_2$ and $G_3$ but the graph can be highly irregular.

show/hide this revision's text 2 added 1403 characters in body

I am going to call the partitions you describe simply equitable (am I missing something?) Here is a graph labelled according to an eigenvector. The red nodes are $+1$ the green are $-1$ and the black are $0$ the corresponding partition is not equitable.

Here is what I think is true: A partition with $k$ parts is equitable iff it supports $k$ linearily independent eigenvectors (for the adjacency matrix $A$ or the Laplacian matrix $L$). Here is a rough sketch of a proof for the case of $A$ (which looks ok to me, but check for yourself) .

Consider a graph and a partition of the $n$ vertices into $k$ classes. The characteristic vectors of the classes are $k$ $0-1$ vectors $v_1,v_2,\dots,v_k$ with sum the all $1$'s vector. They span a dimension $k$ subspace $V$ of $\mathbb{R}^n.$

The partition is defined to be equitable if there are $k^2$ constants $c_{ij}$ such that $Av_j=\sum c_{ij}v_i.$ Mure succinctly: if $AV=V.$ Note that $n_ic_{ij}=n_jc_{ji}.$ Thus(?) $\mathbb{R}^k$ has a basis of eigenvectors for the matrix $C=\left(c_{ij}\right)$ . These lift to $k$ vectors in $\mathbb{R}^n$ which are eigenvectors for $A$ and a basis for $V.$

Conversely, if $V$ has a basis which are eigenvectors of $A$ then it follows that $AV=V.$

old answer left to explain comments:

show/hide this revision's text 1

No. A path with 5 vertices has eigenvector $[1,1,0,-1,-1]$ but the partition is not almost equitable.

More generally, take two graphs $G_1$ and $G_3$ both regular of degree $d$. In addition take an arbitrary graph $G_2$ and connect each vertex of $u \in G_2$ to $s\alpha_u$ vertices of $G_1$ and $t\alpha_u$ vertices of $G_3$ where $\alpha_u$ can depend on $u$. Then this partition of $G=G_1 \cup G_2 \cup G_3$ supports an eigenvector (for $d$) with values $t,0$ and $-s$ respectively on $G_1,G_2$ and $G_3$ but the graph can be highly irregular.