# Tag Info

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