Questions tagged [equitable-partition]
The equitable-partition tag has no usage guidance.
8
questions
0
votes
0
answers
17
views
P-equitable graph partition
I am now conducting a research in regards to p equitable graph partition problem. I need to use LP techniques to kernelize this problem parametrized by vertex cover. In basic definition of such ...
2
votes
2
answers
118
views
Odd partition with extra properties
Can such a set $A=$ {$a_1,.. a_k$} exist, such that:
$\sum_i a_i = 1$ and $a_i $ are rational positive numbers
$k$ is and odd number, and is at least $3$.
We can partition $A$ in two parts of value $...
- 247
4
votes
0
answers
520
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$...
- 493
4
votes
1
answer
551
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 ...
- 2,951
1
vote
1
answer
504
views
almost equitable partitions and spectra
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 ...
- 3,328
2
votes
1
answer
499
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 ...
- 3,328
1
vote
1
answer
243
views
The smallest eigenvalue from an equitable partitions
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) ...
- 6,882
3
votes
1
answer
2k
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 ...
- 6,882