Let denote an undirected, connected, regular graph with vertex set , adjacency matrix , and distinct eigenvalues. Let denote the subalgebra of generated by . We refer to as the adjacency algebra of . In this paper we investigate algebraic and combinatorial structure of for which the adjacency algebra is closed under Hadamard multiplication. In particular, under this simple assumption, we show the following: (i) has a standard basis ; (ii) for every vertex there exists identical distance-faithful intersection diagram of with cells; (iii) the graph is quotient-polynomial; and (iv) if we pick then has distinct eigenvalues if and only if . We describe the combinatorial structure of quotient-polynomial graphs with diameter and distinct eigenvalues. As a consequence of the techniques used in the paper, some simple algorithms allow us to decide whether is distance-regular or not and, more generally, which distance- matrices are polynomial in , giving also these polynomials.
Revised:
Accepted:
Published online:
Keywords: Symmetric association scheme, adjacency algebra, quotient-polynomial graph, intersection diagram.
@article{ALCO_2021__4_6_947_0, author = {Fiol, Miquel A. and Penji\'c, Safet}, title = {On symmetric association schemes and associated quotient-polynomial graphs}, journal = {Algebraic Combinatorics}, pages = {947--969}, publisher = {MathOA foundation}, volume = {4}, number = {6}, year = {2021}, doi = {10.5802/alco.187}, language = {en}, url = {http://www.numdam.org/articles/10.5802/alco.187/} }
TY - JOUR AU - Fiol, Miquel A. AU - Penjić, Safet TI - On symmetric association schemes and associated quotient-polynomial graphs JO - Algebraic Combinatorics PY - 2021 SP - 947 EP - 969 VL - 4 IS - 6 PB - MathOA foundation UR - http://www.numdam.org/articles/10.5802/alco.187/ DO - 10.5802/alco.187 LA - en ID - ALCO_2021__4_6_947_0 ER -
%0 Journal Article %A Fiol, Miquel A. %A Penjić, Safet %T On symmetric association schemes and associated quotient-polynomial graphs %J Algebraic Combinatorics %D 2021 %P 947-969 %V 4 %N 6 %I MathOA foundation %U http://www.numdam.org/articles/10.5802/alco.187/ %R 10.5802/alco.187 %G en %F ALCO_2021__4_6_947_0
Fiol, Miquel A.; Penjić, Safet. On symmetric association schemes and associated quotient-polynomial graphs. Algebraic Combinatorics, Volume 4 (2021) no. 6, pp. 947-969. doi : 10.5802/alco.187. http://www.numdam.org/articles/10.5802/alco.187/
[1] Algebraic characterizations of regularity properties in bipartite graphs, European J. Combin., Volume 34 (2013) no. 8, pp. 1223-1231 | DOI | MR | Zbl
[2] Corrigendum to “Algebraic characterizations of regularity properties in bipartite graphs” [European J. Combin. 34 (2013) 1223–1231][MR3082194], European J. Combin., Volume 38 (2014), pp. 130-132 | DOI | MR | Zbl
[3] Linear algebra done right, Undergraduate Texts in Mathematics, Springer, Cham, 2015, xviii+340 pages | DOI | MR | Zbl
[4] Association schemes. Designed experiments, algebra and combinatorics, Cambridge Studies in Advanced Mathematics, 84, Cambridge University Press, Cambridge, 2004, xviii+387 pages | DOI | MR
[5] Algebraic combinatorics. I, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1984, xxiv+425 pages | MR | Zbl
[6] Algebraic graph theory, Cambridge Tracts in Mathematics, Cambridge University Press, London, 1974 no. 67, vii+170 pages | MR | Zbl
[7] On linear associative algebras corresponding to association schemes of partially balanced designs, Ann. Math. Statist., Volume 30 (1959), pp. 21-38 | DOI | MR | Zbl
[8] Distance-regular graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], 18, Springer-Verlag, Berlin, 1989, xviii+495 pages | DOI | MR | Zbl
[9] Spectra of graphs, Universitext, Springer, New York, 2012, xiv+250 pages | DOI | MR | Zbl
[10] Designs, graphs, codes and their links, London Mathematical Society Student Texts, 22, Cambridge University Press, Cambridge, 1991, x+240 pages | DOI | MR | Zbl
[11] The Terwilliger algebra of a distance-regular graph that supports a spin model, J. Algebraic Combin., Volume 21 (2005) no. 3, pp. 289-310 | DOI | MR | Zbl
[12] On almost distance-regular graphs, J. Combin. Theory Ser. A, Volume 118 (2011) no. 3, pp. 1094-1113 | DOI | MR | Zbl
[13] A general method to obtain the spectrum and local spectra of a graph from its regular partitions, Electron. J. Linear Algebra, Volume 36 (2020), pp. 446-460 | DOI | MR
[14] Three-class association schemes, J. Algebraic Combin., Volume 10 (1999) no. 1, pp. 69-107 | DOI | MR | Zbl
[15] The spectral excess theorem for distance-regular graphs: a global (over)view, Electron. J. Combin., Volume 15 (2008) no. 1, Research Paper 129, 10 pages | DOI | MR | Zbl
[16] Distance-regular graphs, Dynamic Surveys, Electron. J. Combin., 2016, 156 pages | DOI | Zbl
[17] An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl. (1973) no. 10, p. vi+97 | MR | Zbl
[18] Association schemes and coding theory, IEEE Trans. Inform. Theory, Volume 44 (1998) no. 6, pp. 2477-2504 (Information theory: 1948–1998) | DOI | MR | Zbl
[19] -polynomial structures for association schemes and distance-regular graphs, Ph. D. Thesis, The University of Wisconsin - Madison (1995) | MR
[20] Permutation group approach to association schemes, European J. Combin., Volume 30 (2009) no. 6, pp. 1456-1476 | DOI | MR | Zbl
[21] Algebraic decompositions of commutative association schemes, J. Algebra, Volume 96 (1985) no. 1, pp. 211-229 | DOI | MR | Zbl
[22] A lower bound for the discriminant of polynomials related to Chebyshev polynomials, Discrete Math., Volume 344 (2021) no. 3, 112235, 6 pages | DOI | MR | Zbl
[23] Eigenvalue interlacing and weight parameters of graphs, Linear Algebra Appl., Volume 290 (1999) no. 1-3, pp. 275-301 | DOI | MR | Zbl
[24] On pseudo-distance-regularity, Linear Algebra Appl., Volume 323 (2001) no. 1-3, pp. 145-165 | DOI | MR | Zbl
[25] Algebraic characterizations of distance-regular graphs, Discrete Math., Volume 246 (2002) no. 1-3, pp. 111-129 Formal power series and algebraic combinatorics (Barcelona, 1999) | DOI | MR | Zbl
[26] Quotient-polynomial graphs, Linear Algebra Appl., Volume 488 (2016), pp. 363-376 | DOI | MR | Zbl
[27] A simple proof of the spectral excess theorem for distance-regular graphs, Linear Algebra Appl., Volume 432 (2010) no. 9, pp. 2418-2422 | DOI | MR
[28] From local adjacency polynomials to locally pseudo-distance-regular graphs, J. Combin. Theory Ser. B, Volume 71 (1997) no. 2, pp. 162-183 | DOI | MR | Zbl
[29] Locally pseudo-distance-regular graphs, J. Combin. Theory Ser. B, Volume 68 (1996) no. 2, pp. 179-205 | DOI | MR | Zbl
[30] On a version of the spectral excess theorem, Electron. J. Graph Theory Appl. (EJGTA), Volume 8 (2020) no. 2, pp. 391-400 | DOI | MR
[31] Coherent algebras and the graph isomorphism problem, Discrete Appl. Math., Volume 25 (1989) no. 1-2, pp. 73-98 Combinatorics and complexity (Chicago, IL, 1987) | DOI | MR | Zbl
[32] Algebraic combinatorics, Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993, xvi+362 pages | MR | Zbl
[33] On quasi-strongly regular graphs, Linear Multilinear Algebra, Volume 54 (2006) no. 6, pp. 437-451 | DOI | MR | Zbl
[34] Coherent configurations. I. Ordinary representation theory, Geometriae Dedicata, Volume 4 (1975) no. 1, pp. 1-32 | DOI | MR | Zbl
[35] Coherent algebras, Linear Algebra Appl., Volume 93 (1987), pp. 209-239 | DOI | MR | Zbl
[36] On the polynomial of a graph, Amer. Math. Monthly, Volume 70 (1963), pp. 30-36 | DOI | MR | Zbl
[37] Matrix analysis, Cambridge University Press, Cambridge, 2013, xviii+643 pages | MR | Zbl
[38] On coherent algebras and strict algebras, J. Algebra, Volume 13 (1969), pp. 299-307 | DOI | MR | Zbl
[39] Primitivity of permutation groups, coherent algebras and matrices, J. Combin. Theory Ser. A, Volume 98 (2002) no. 1, pp. 210-217 | DOI | MR | Zbl
[40] Commutative association schemes obtained from twin prime powers, Fermat primes, Mersenne primes, Finite Fields Appl., Volume 63 (2020), 101631, 22 pages | DOI | MR | Zbl
[41] Directed strongly regular graphs obtained from coherent algebras, Linear Algebra Appl., Volume 377 (2004), pp. 83-109 | DOI | MR | Zbl
[42] Algebraic combinatorics in mathematical chemistry. Methods and algorithms. I. Permutation groups and coherent (cellular) algebras, Match (1999) no. 40, pp. 7-138 | MR | Zbl
[43] Matrix analysis for scientists & engineers, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005, xiv+157 pages | DOI | MR | Zbl
[44] A course in combinatorics, Cambridge University Press, Cambridge, 2001, xiv+602 pages | DOI | MR | Zbl
[45] On bipartite distance-regular graphs with exactly one non-thin -module with endpoint two, European J. Combin., Volume 64 (2017), pp. 125-137 | DOI | MR | Zbl
[46] On bipartite distance-regular graphs with exactly two irreducible T-modules with endpoint two, Linear Algebra Appl., Volume 515 (2017), pp. 275-297 | DOI | MR | Zbl
[47] On the Terwilliger algebra of bipartite distance-regular graphs with and , Linear Algebra Appl., Volume 496 (2016), pp. 307-330 | DOI | MR | Zbl
[48] An -invariant subspace for bipartite distance-regular graphs with exactly two irreducible -modules with endpoint 2, both thin, J. Algebraic Combin., Volume 48 (2018) no. 3, pp. 511-548 | DOI | MR | Zbl
[49] The theory of error-correcting codes. I, North-Holland Mathematical Library, 16, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977, p. i-xv and 1–369 | MR
[50] Scaffolds: a graph-theoretic tool for tensor computations related to Bose-Mesner algebras, Linear Algebra Appl., Volume 619 (2021), pp. 50-106 | DOI | MR | Zbl
[51] Commutative association schemes, European J. Combin., Volume 30 (2009) no. 6, pp. 1497-1525 | DOI | MR | Zbl
[52] On bipartite -polynomial distance-regular graphs with diameter 9, 10, or 11, Electron. J. Combin., Volume 25 (2018) no. 1, P1.52, 12 pages | DOI | MR | Zbl
[53] On Lee association schemes over and their Terwilliger algebra, Linear Algebra Appl., Volume 510 (2016), pp. 311-328 | DOI | MR | Zbl
[54] Terwilliger algebras of wreath products of association schemes, Linear Algebra Appl., Volume 493 (2016), pp. 146-163 | DOI | MR | Zbl
[55] Krein conditions and near polygons, J. Combin. Theory Ser. A, Volume 54 (1990) no. 2, pp. 201-209 | DOI | MR | Zbl
[56] On the Terwilliger algebra of bipartite distance-regular graphs with and , Discrete Math., Volume 340 (2017) no. 3, pp. 452-466 | DOI | MR | Zbl
[57] On the Terwilliger algebra of bipartite distance-regular graphs, Ph. D. Thesis, University of Primorska, Koper (2019), x+107 pages (https://osebje.famnit.upr.si/~penjic/research/)
[58] 2-walk-regular dihedrants from group divisible designs, Electron. J. Combin., Volume 23 (2016) no. 2, P2.51, 11 pages | DOI | MR | Zbl
[59] Linear algebra, Graph connections (Oxford Lecture Ser. Math. Appl.), Volume 5, Oxford Univ. Press, New York, 1997, pp. 86-99 | MR | Zbl
[60] Weighted association schemes, fusions, and minimal coherent closures, J. Algebraic Combin., Volume 41 (2015) no. 3, pp. 785-815 | DOI | MR | Zbl
[61] On -fold covers of coherent configurations, Ars Math. Contemp., Volume 14 (2018) no. 2, pp. 397-413 | DOI | MR | Zbl
[62] Equitable partitions, coherent algebras and random walks: applications to the correlation structure of landscapes, Match (1999) no. 40, pp. 215-261 | MR | Zbl
[63] Coherent configurations and triply regular association schemes obtained from spherical designs, J. Combin. Theory Ser. A, Volume 117 (2010) no. 8, pp. 1178-1194 | DOI | MR | Zbl
[64] The subconstituent algebra of an association scheme. I, J. Algebraic Combin., Volume 1 (1992) no. 4, pp. 363-388 | DOI | MR | Zbl
[65] The subconstituent algebra of an association scheme. II, J. Algebraic Combin., Volume 2 (1993) no. 1, pp. 73-103 | DOI | MR | Zbl
[66] The subconstituent algebra of an association scheme. III, J. Algebraic Combin., Volume 2 (1993) no. 2, pp. 177-210 | DOI | MR | Zbl
[67] A new inequality for distance-regular graphs, Discrete Math., Volume 137 (1995) no. 1-3, pp. 319-332 | DOI | MR | Zbl
[68] Algebraic graph theory (MATH 846) (January 2009) (Lecture notes, University of Wisconsin, https://www.math.wisc.edu/~terwilli/teaching.html)
[69] A reduction of a graph to canonical form and an algebra arising during this reduction, NTI, Volume 9 (1968), pp. 12-16 https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf
[70] The Kronecker product of graphs, Proc. Amer. Math. Soc., Volume 13 (1962), pp. 47-52 | DOI | MR | Zbl
[71] On distance-regularity in graphs, J. Combin. Theory Ser. B, Volume 32 (1982) no. 2, pp. 156-161 | DOI | MR | Zbl
[72] Pseudo-direct sums and wreath products of loose-coherent algebras with applications to coherent configurations, Linear Algebra Appl., Volume 530 (2017), pp. 202-219 | DOI | MR | Zbl
Cited by Sources: