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/

[1] T.Sunada, “Riemannian Coverings and Isospectral Manifolds”, Ann. Math., 121 (1985), 169–186 | DOI | MR | Zbl

[2] R. Brooks, “Non-Sunada graphs”, Annales de l'institut Fourier, 49:2 (1999), 707–725 | DOI | MR | Zbl

[3] M. Cvetkovic, M. Doob, I. Gootman, A. Targasev, Recent Results in the Theory of Graph Spectra, Ann. Disc. Math., 36, North Holland, 1988 | MR | Zbl

[4] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-regular Graphs, Springer-Verlag, Berlin, 1989 | MR | Zbl

[5] J. Hemmeter, “Distance-Regular Graphs and Halved Graphs”, Europ. J. Combinatorics, 7 (1986), 119–129 | DOI | MR | Zbl

[6] V. Ustimenko, “On some properties of the geometries of the Chevalley groups and their generalizations”, Investigations in Algebraic Theory of Combinatorial Objects, Kluwer, Dordrecht, 1992, 112–119

[7] Edwin R. van Dam, Jack H. Koolen, Hajime Tanaka, “Distance Regular Graphs”, Dynamic Survey, The Electronic Journal of Combinatorics, 2016, DS22 | Zbl

[8] C. T. Benson, “Minimal regular graphs of girths eight and twelve”, Canad. J. Math., 26 (1966), 1091–1094 | DOI | MR

[9] J.Tits, “Sur la trialite et certains groupes qui s'en deduisent”, Inst. Hautes Etudes Sci. Publ. Math., 2 (1959), 13–60 | DOI | MR | Zbl

[10] V. V. Zdan-Pushkin, V. A. Ustimenko, “On the maximality of certain classical transformation groups”, Voprosi teorii grupp i gomologicheskoi algebry, 1985, 125–139 | MR

[11] V. V. Zdan-Pushkin, V. A. Ustimenko, “Maximality of finite classical groups acting on the totally isotropic subspaces”, Selecta Mathematica Sovetica, 9:4 (1990), 339–354 | MR

[12] J Dieudonné, Sur les groupes classiques, Hermann, Paris, 1948 | MR | Zbl

[13] V. V. Zhdan-Pushkin, V. A. Ustimenko, “Classical groups and metric association schemes”, Kibernetika, 6 (1986), 83–94

[14] R. Carter, Simple group of Lie type, Wiley, 1989 | MR

[15] Handbook of incidence geometry, eds. F. Buekenhout, Amsterdam, 1995 | MR | Zbl

[16] A. Borovik, I. Gelfand, N. White, “Combinatorial Flag Varieties”, Journal of Combinatorial Theory, Series A, 91 (2000), 111–136 | DOI | MR | Zbl

[17] V. Ustimenko, “On the varieties of parabolic subgroups, their generalisations and combinatorial applications”, Acta Applicandae Mathematicae, 52 (1998), 223–238 | DOI | MR | Zbl

[18] A. Brouwer, D. Pasechnik, “Two distance-regular graphs”, J. Algebraic Combin., 36 (2012) | DOI | MR | Zbl

[19] A. Pasini, S. Yoshiara, “New distance regular graphs arising from dimensional dual hyperovals”, European J. Combin., 22 (2001), 547–560 | DOI | MR | Zbl

[20] A. E. Brouwer, Corrections and additions to the book “Distance-regular Graphs”, October 2008 http://www.win.tue.nl/<nobr>$\sim$</nobr>aeb/drg/BCN-ac.ps.gz

[21] E. R. van Dam, J. H. Koolen, “A new family of distance-regular graphs with unbounded diameter”, Invent. Math., 162 (2005), 189–193 | DOI | MR | Zbl

[22] T Fujisaki, J. H. Koolen, M. Tagami, “Some properties of the twisted Grassmann graphs”, Innov. Incidence Geom., 3 (2006), 81–86 | DOI | MR

[23] S. Bang, T. Fujisaki, J. H. Koolen, “The spectra of the local graphs of the twisted Grassmann graphs”, European J. Combin., 30 (2009), 638–654 | DOI | MR | Zbl

[24] P. Terwilliger, “The subconstituent algebra of an association scheme, I”, J. Algebraic Combin., 1 (1992), 363–388 ; II, J. Algebraic Combin., 2 (1993), 73–103 ; III, J. Algebraic Combin., 2 (1993), 177–210 | DOI | MR | Zbl | DOI | MR | Zbl | DOI | MR | Zbl

[25] D. Jungnickel, V. Tonchev, “Polarities, quasi-symmetric designs and Hamada's conjecture”, Des. Codes Cryptogr., 51 (2009), 131–140 | DOI | MR | Zbl

[26] A. Munemasa, V. D. Tonchev, “The twisted Grassmann graph is the block graph of a design”, Innov. Incidence Geom., 12 (2011), 1–6 ; arXiv: 0906.4509 | DOI | MR | Zbl

[27] A. Munemasa, Godsil-McKay switching and twisted Grassmann graphs, preprint, 2015, arXiv: 1512.09232 | MR

[28] A. E. Brouwer, W. H. Haemers, Spectra of Graphs, Springer, New York, 2012 | MR | Zbl

[29] K. Mehlhorn, “A faster approximation algorithm for the steiner problem in graphs”, Inf. Process. Lett., 27:3 (1988), 125–128 | DOI | MR | Zbl

[30] M. Erwig, “The graph Voronoi diagram with applications”, Networks, 36:3 (2000), 156–163 | 3.0.CO;2-L class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[31] V. Ustimenko, A. Woldar, “A geometric approach to orbital recognition in Chevalley-type coherent configurations and association schemes”, Australas. J. Combin., 67:2 (2017), 166–202 | MR | Zbl

[32] N. Bourbaki, Lie Groups and Lie Algebras, Chapters 1–9, Springer, 1998–2008 | MR | Zbl

[33] E. Bannai, T. Ito, Algebraic Combinatorics, 1984, 449 pp. | MR | Zbl

[34] I. Faradjev M. Klin, M. Muzychuk, “Cellular Rings and Groups of Automorphisms of Graphs”, Investigations in Algebraic Theory of Combinatorial Objects, eds. Faradzev I. A., Ivanov A. A., Klin M., Woldar A. J., Springer, 1994, 1–152 | MR

[35] E. Hewitt, K.Ross, Abstract harmonic analysis, v. 2, Structure and analysis for compact groups. Analysis on locally compact abelian groups, Springer, 1970, 392 pp. | MR | Zbl

[36] E. Hewitt, K. Ross, Abstract Harmonic Analysis, v. 1, Structure of Topological Groups. Integration Theory, Group Representations, Springer, 1994, 540 pp. | MR

[37] V. Ustimenko, Urszula Romaćzuk, Finite geometries, LDPC codes and Cryptography, Maria Curie-Sklodowska University, Institute of Computer Science, 2012, online access at https://www.informatyka.umcs.lublin.pl