There have been questions lately about almost equitable partitions in graphs, for example this one which provides the definition.) Every equitable partition is almost equitable. The converse is true for regular graphs but not in general. Equitable partitions are useful for understanding eigenvalues of (the adjacency matrix of) certain graphs. There are many nice examples of equitable partitions coming from distance regular graphs, graphs with a non-trivial automorphism etc. I looked a bit and found papers about graphs with almost equitable partitions which were not equitable, but mainly as examples that it could happen. Hence

What are some interesting examples of graphs with almost equitable partitions which are not equitable? In particular (but not exclusively) infinite familes.

For me interesting would mean revealing some structure not obvious or just attractive in some way( vague I know).

As an experiment I considered a $5 \times 5$ grid with $25$ points of degrees $2,3$ and $4$. There are equitable partitions corresponding to orbits of the automorphism group (quarter rotation,half rotation,flip either of two ways). So all these have at least $6$ classes. The adjacency matrix has $13$ eigenvalues, some double, all in $\mathbb{Z}[\sqrt{3}]$. For the Laplacian there are $14$ eigenvalues including $4$ with multiplicity $4$, all are in $\mathbb{Z}[\sqrt{5}]$. The one only almost equitable partition I saw so far is in 3 classes, top and bottom rows,rows 2 and 4, middle row (and the column version of that.)

Maybe that was the wrong example, but what is a better one?


Well, my favourite example: There has been some research on the Laplacians on infinite graphs lately, say here and here. The authors deduce a few decompositions for the Laplacians on (usually infinite) trees and "perturbed trees" under certain symmetry assumptions, and they even draw a lot of pictures to show them more clearly. You will easily see that most of their graphs have natural a.e. partitions (usually induced by the distance to the root) which are not equitable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.