# Questions tagged [equitable-partition]

The tag has no usage guidance.

6 questions
Filter by
Sorted by
Tagged with
248 views

### Is this partition problem strongly NP-complete?

Some computational problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's Graph Isomorphism result) while the ...
290 views

### Orthogonal similarity of adjacency matrices of graphs which are cospectral and have a common equitable partition

Let $G$ and $H$ be two undirected graphs of the same order (i.e., they have the same number of vertices). Denote by $A_G$ and $A_H$ the corresponding adjacency matrices. Furthermore, denote by $\bar G$...
1k views

### equitable partitions

It is well known that if $\pi$ is an equitable partition of a graph, then the spectrum of the corresponding partition matrix is a subset of the spectrum of the graph's matrix (where the matrix can be ...
429 views

### algorithmic almost equitable partitioning

Let $G$ be a graph -- possibly infinite, but I will be glad to learn a positive result even in the finite case. Then the trivial partition (i.e., one cell coinciding with the whole $G$) is clearly ...
Suppose that $G$ is a connected graph with equitable partition $\pi$. Then the eigenvalues of the divisor multigraph $G / \pi$ are all eigenvalues of $G$. (Perhaps excluding some pathological cases) ...
If a graph $G$ has an equitable partition, then its charachteristic polynomial (for the adjacency matrix) has a divisor that can be seen as the characteristic polynomial (for the adjacency matrix) of ...