4

There are infinitely many counterexamples. Let $\pi$ be the distance partition relative to a vertex in a strongly regular graph. Then $\pi$ is equitable and $G/\pi$ is a path, so its eigenvalues are all simple. But if $G$ is not bipartite, its least eigenvalue is not simple.


2

The question is fairly broad. I can say a number of things, but none of them are very deep. For a regular graph the largest eigenvalue of the adjacency matrix, $A$, is the common degree with eigenvector $\mathbf{1}$, the all $1$'s vector. So any partition supports that eigenvector. We could discuss the negative adjacency matrix $-A$ and now the smallest ...


1

It seems, that there exists a pseudo-polynomial time algorithm for your problem. Denote by $N$ the sum of $S$. Add $N \cdot |S|$ to each element of $S$. This allows us to not carry about the cardinality restriction. Consider a square boolean table $T$ of size $N^2 \cdot |S|$ with the following sense: $T(X,Y)=1$ if there exist two disjoint subsets $S_X$...


1

I think the real problem is that the obvious notion of ``Laplacian walk-regular'' implies that the graph must be regular. The proof of the ``old result'' can be modified to yield the following. Let $L$ be the Laplacian of the graph $X$, let $v$ be a vertex in $X$ and let $L_v$ denote the matrix we get by deleting the $v$-row and $v$-column from $L$. (So $...


1

The definition to which you link says $\forall i,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 the component $V_j$ does not depend on the choice of $v$. Am I correct that that is the definition of equitable whereas almost-equitable restricts to $i \ne j$? You ...


Only top voted, non community-wiki answers of a minimum length are eligible