On small world non-Sunada twins and cellular Voronoi diagrams

Special infinite families of regular graphs of unbounded degree and of bounded diameter (small world graphs) are considered. Two families of small world graphs $G_i$ and $H_i$ form a family of non-Sunada twins if $G_i$ and $H_i$ are isospectral of bounded diameter but groups $\mathrm{Aut}(G_i)$ and $\mathrm{Aut}(H_i)$ are nonisomorphic. We say that a family of non-Sunada twins is unbalanced if each $G_i$ is edge-transitive but each $H_i$ is edge-intransitive. If all $G_i$ and $H_i$ are edge-transitive we have a balanced family of small world non-Sunada twins. We say that a family of non-Sunada twins is strongly unbalanced if each $G_i$ is edge-transitive but each $H_i$ is edge-intransitive. We use term edge disbalanced for the family of non-Sunada twins such that all graphs $G_i$ and $H_i$ are edge-intransitive. We present explicit constructions of the above defined families. Two new families of distance-regular—but not distance-transitive—graphs will be introduced.