Geodesic
On small world non-Sunada twins and cellular Voronoi diagrams
Algebra and discrete mathematics, Tome 30 (2020) no. 1, pp. 118-142

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: Laplacians, isospectral graphs, small world graphs, distance-regular graphs, non-Sunada constructions, graph Voronoi diagram, thin Voronoi cells. 
@article{ADM_2020_30_1_a9,
     author = {V. Ustimenko},
     title = {On small world {non-Sunada} twins and cellular {Voronoi} diagrams},
     journal = {Algebra and discrete mathematics},
     pages = {118--142},
     publisher = {mathdoc},
     volume = {30},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ADM_2020_30_1_a9/}
}
TY  - JOUR
AU  - V. Ustimenko
TI  - On small world non-Sunada twins and cellular Voronoi diagrams
JO  - Algebra and discrete mathematics
PY  - 2020
SP  - 118
EP  - 142
VL  - 30
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ADM_2020_30_1_a9/
LA  - en
ID  - ADM_2020_30_1_a9
ER  - 
%0 Journal Article
%A V. Ustimenko
%T On small world non-Sunada twins and cellular Voronoi diagrams
%J Algebra and discrete mathematics
%D 2020
%P 118-142
%V 30
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ADM_2020_30_1_a9/
%G en
%F ADM_2020_30_1_a9
V. Ustimenko. On small world non-Sunada twins and cellular Voronoi diagrams. Algebra and discrete mathematics, Tome 30 (2020) no. 1, pp. 118-142. http://geodesic.mathdoc.fr/item/ADM_2020_30_1_a9/