RESEARCH ARTICLE

On small world non-Sunada twins and cellular Voronoi diagrams

V. Ustimenko<sup>ab

a</sup> Institute of Telecommunications and Global Information Space, NAS of Ukraine, Ukraine
^b Institute of Mathematics, Maria Curie-Skłdowska University, Poland

Abstract: 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.

MSC: 05C50, 05C82, 51E24

Received: 20.02.2019
Revised: 12.12.2020

Language: English

DOI: 10.12958/adm1343

Bibliographic databases:

• 
•