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

#### Related Tags

equitable-partition × 6graph-theory × 5

spectral-graph-theory × 2

co.combinatorics × 1

linear-algebra × 1

algorithms × 1

computational-complexity × 1

eigenvalues × 1

partitions × 1

algebraic-graph-theory × 1

orthogonal-matrices × 1

isospectrality × 1