On small world non-Sunada twins and cellular Voronoi diagrams

• Datum: 2020
• 1. Verfasser: Ustimenko, V.
• Format: Artikel
• Sprache: English
• Veröffentlicht: Lugansk National Taras Shevchenko University 2020
• Schlagworte: Laplacians; isospectral graphs; small world graphs; distance-regular graphs; non-Sunada constructions; graph Voronoi diagram; thin Voronoi cells; 05C50; 05C82; 51E24
• Online Zugang: https://admjournal.luguniv.edu.ua/index.php/adm/article/view/1343
• Назва журналу: Algebra and Discrete Mathematics

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 \(Aut(G_i)\) and \(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.