×

On small world non-Sunada twins and cellular Voronoi diagrams. (English) Zbl 1473.05191

Summary: 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 \(\operatorname{Aut}(G_i)\) and \(\operatorname{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.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
51E24 Buildings and the geometry of diagrams
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] T.Sunada,Riemannian Coverings and Isospectral Manifolds, Ann. Math., 121 (1985), 169-186. · Zbl 0585.58047
[2] R. Brooks,Non-Sunada graphs, Annales de l’institut Fourier, tome 49, no 2 (1999), p. 707-725. · Zbl 0926.58021
[3] M. Cvetkovic, M. Doob, I. Gootman, A. Targasev,Theory of Graph Spectra, Ann. Disc. Math. 36, North Holland, 1988. · Zbl 0634.05054
[4] A. E. Brouwer, A. M. Cohen and A. Neumaier,Distance-regular Graphs, SpringerVerlag, Berlin, 1989. · Zbl 0747.05073
[5] J. Hemmeter,Distance-Regular Graphs and Halved Graphs, Europ. J. Combinatorics (1986) 7, 119-129. · Zbl 0606.05041
[6] V. Ustimenko,On some properties of the geometries of the Chevalley groups and their generalizations, Investigations in Algebraic Theory of Combinatorial Objects,
[7] Edwin R. van Dam, Jack H. Koolen, Hajime Tanaka,Distance Regular Graphs, The Electronic Journal of Combinatorics, Dynamic Survey, DS22, 2016 · Zbl 1335.05062
[8] C. T. Benson,Minimal regular graphs of girths eight and twelve, Canad. J. Math. 26 (1966), 1091-1094. · Zbl 0146.45701
[9] J.Tits,Sur la trialite et certains groupes qui s’en deduisent, Inst. Hautes Etudes Sci. Publ. Math. 2 (1959), 13-60. · Zbl 0088.37204
[10] V. V. Zdan-Pushkin, V. A. Ustimenko,On the maximality of certain classical transformation groups, Voprosi teorii grupp i gomologicheskoi algebry, 1985, pp. · Zbl 0628.20007
[11] V.V. Zdan-Pushkin, V. A. Ustimenko,Maximality of finite classical groups acting on the totally isotropic subspaces, Selecta Mathematica Sovetica, vol. 9, no. 4, 1990, · Zbl 0725.20003
[12] J Dieudonné,Sur les groupes classiques, Paris: Hermann, 1948. · Zbl 0037.01304
[13] V. V. Zhdan-Pushkin, V.A. Ustimenko,Classical groups and metric association schemes, Kibernetika, 6, 1986, pp. 83-94. · Zbl 0643.05019
[14] R. Carter,Simple group of Lie type, Wiley, 1989. · Zbl 0723.20006
[15] F. Buekenhout, ed.,Handbook of incidence geometry, Amsterdam: 1995. · Zbl 0821.00012
[16] A, Borovik, I. Gelfand, N. White,Combinatorial Flag Varieties, Journal of Combinatorial Theory, Series A, 91, (2000) 111-136. · Zbl 0964.05019
[17] V. Ustimenko,On the varieties of parabolic subgroups, their generalisations and combinatorial applications, Acta Applicandae Mathematicae, 52 , 1998, 223-238. · Zbl 0915.20024
[18] A. Brouwer, D. Pasechnik,Two distance-regular graphs, J. Algebraic Combin., 36 (2012). · Zbl 1254.05199
[19] A, Pasini, S. Yoshiara,New distance regular graphs arising from dimensional dual hyperovals, European J. Combin. 22 (2001), 547-560. · Zbl 1004.51017
[20] A.E. Brouwer,Corrections and additions to the book “Distance-regular Graphs”, http://www.win.tue.nl/ aeb/drg/BCN-ac.ps.gz(October 2008).
[21] E. R. van Dam, J, H. Koolen,A new family of distance-regular graphs with unbounded diameter, Invent. Math. 162 (2005), 189-193. · Zbl 1074.05092
[22] T Fujisaki, J. H. Koolen, M. Tagami,Some properties of the twisted Grassmann graphs, Innov. Incidence Geom. 3 (2006), 81-86. · Zbl 1111.05099
[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. · Zbl 1172.05333
[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. · Zbl 0785.05090
[25] D. Jungnickel, V. Tonchev,Polarities, quasi-symmetric designs and Hamada’s conjecture, Des. Codes Cryptogr. 51 (2009), 131-140. · Zbl 1247.05032
[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. · Zbl 1293.05020
[27] A. Munemasa,Godsil-McKay switching and twisted Grassmann graphs, preprint (2015); arXiv:1512.09232. · Zbl 1367.05026
[28] A. E. Brouwer, W. H. Haemers,Spectra of Graphs, Springer, New York, 2012. · Zbl 1231.05001
[29] K. Mehlhorn,A faster approximation algorithm for the steiner problem in graphs, Inf. Process. Lett., 1988, 27 (3), 125-128. · Zbl 0635.68071
[30] M. Erwig,The graph Voronoi diagram with applications, Networks, vol. 36 (2000) no. 3, pp. 156-163. · Zbl 0963.68148
[31] V. Ustimenko, A. Woldar,A geometric approach to orbital recognition in Chevalleytype coherent configurations and association schemes, Australas. J. Combin. 67 · Zbl 1375.05276
[32] N. Bourbaki,Lie Groups and Lie Algebras, Chapters 1 - 9, Springer, 1998-2008. “adm-n3” — 2021/1/4 — 9:14 — page 142 — #148
[33] E. Bannai, T. Ito, Algebraic Combinatorics. 1984, 449 p. · Zbl 0555.05019
[34] I. Faradjev M. Klin, M. Muzychuk,Cellular Rings and Groups of Automorphisms of Graphs, In “Investigations in Algebraic Theory of Combinatorial Objects” (editors:
[35] E. Hewitt, K.Ross,Abstract harmonic analysis, vol.2, Structure and analysis for compact groups. Analysis on locally compact abelian groups, Springer, 1970, 392 p. · Zbl 0213.40103
[36] E. Hewitt, K. Ross,Abstract Harmonic Analysis: Volume 1, Structure of Topological Groups., Integration Theory, Group Representations, Springer, 1994, 540 p. · Zbl 0837.43002
[37] V. Ustimenko, Urszula Romaćzuk,Finite geometries, LDPC codes and Cryptography, Maria Curie-Sklodowska University, Institute of Computer Science, 2012, (on line access www: informatyka.umcs.lublin.pl)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.