On small world non-Sunada twins and cellular Voronoi diagrams

• Datum: 2020
• 1. Verfasser: Ustimenko, V.
• Format: Artikel
• Sprache: English
• Veröffentlicht: Інститут прикладної математики і механіки НАН України 2020
• Schriftenreihe: Algebra and Discrete Mathematics
• Online Zugang: https://nasplib.isofts.kiev.ua/handle/123456789/188557
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Zitieren: On small world non-Sunada twins and cellular Voronoi diagrams / V. Ustimenko // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 1. — С. 118–142. — Бібліогр.: 37 назв. — англ.

Special infinite families of regular graphs of unbounded degree and of bounded diameter (small world graphs) are considered. Two families of small world graphs Gi and Hi form a family of non-Sunada twins if Gi and Hi are isospectral of bounded diameter but groups Aut(Gi) and Aut(Hi) are nonisomorphic. We say that a family of non-Sunada twins is unbalanced if each Gi is edge-transitive but each Hi is edge-intransitive. If all Gi and Hi 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 Gi is edge-transitive but each Hi is edge-intransitive. We use term edge disbalanced for the family of non-Sunada twins such that all graphs Gi and Hi 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.