Sesión Matemática Discreta y Teoría de JuegosCommutative Distance-Regularity: Algebraic Hierarchies and Cayley Graph Constructions
Agustín Oromí
CIEM-FAMAF-UNC, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Given a graph \(G\), its distance matrices \(A_0, A_1, \dots, A_d\) record which pairs of vertices are at each distance. That is, the matrix \(A_\delta\) has a \(1\) in position \(u,v\) if \(u\) and \(v\) are at distance \(\delta\) in \(G\), and a \(0\) otherwise. Several families with increasing metric symmetry are defined over these matrices: a graph is DR (distance-regular) if the number of vertices that are simultaneously at distance \(i\) from \(u\) and at distance \(j\) from \(v\) depends solely on the distance between \(u\) and \(v\); it is DMR if for each vertex \(u\), the average of \(\vert{}\Gamma_i(u) \cap \Gamma_j(v)\vert{}\) over the neighbors \(v\) at distance \(h\) from \(u\) depends only on \(h,i,j\) and not on \(u\); it is CDDR if the distance matrices commute with each other (\(A_i A_j = A_j A_i\)); and it is DP if each \(A_i\) is a polynomial in \(A_1\). Conde et al. [1] established the strict hierarchy \(\{\mathrm{DR}\} \subsetneq \{\mathrm{DP}\} \subsetneq \{\mathrm{CDDR}\} \subsetneq \{\mathrm{DDR}\}\), with \(\{\mathrm{DMR}\}\) and \(\{\mathrm{CDDR}\}\) being incomparable, and posed as open questions whether CDDR is closed under graph products and whether proper sub- or superclasses exist.In this work, we answer both questions. By deriving explicit formulas for the distance matrices in terms of Kronecker products, we prove that DDR, CDDR, and DMR are closed under the strong, Cartesian, and lexicographic products, with the converses holding in all cases. For the tensor product, none of these classes is closed; we then introduce the Distance Walk Regular (DWR) class—where the existence of a walk of length \(k\) between \(u\) and \(v\) depends only on \(d(u,v)\)—and prove that under the additional hypothesis of DWR, inheritance is restored. Furthermore, we introduce \(i\)-CDDR graphs, obtaining the strict hierarchy \(\{\mathrm{CDDR}\} \subsetneq \{1\text{-CDDR}\} \subsetneq \{\mathrm{DDR}\}\). Finally, in Cayley graphs \(\mathrm{Cay}(H,S)\), we prove that \(A_i A_j = A_j A_i\) if and only if \(\Gamma_i(e)\Gamma_j(e) = \Gamma_j(e)\Gamma_i(e)\) where \(\Gamma_i(e)\) is the subset of \(H\) consisting of all elements at distance \(i\) from the identity element \(e\), and \(\Gamma_j(e)\Gamma_i(e) = \{ r_j r_i \mid r_j \in \Gamma_j(e), r_i \in \Gamma_i(e) \}\), characterizing CDDR in purely group-theoretic terms. Using these products as lifting operators, we construct infinite families in each region of the extended hierarchy.
Trabajo en conjunto con: Adrián Pastine (Universidad Nacional de San Luis).
Referencias
[1] Conde, C. M., Dratman, E., Moyano, V. A., & Pastine, A. (2026). Commutative distance degree-regular graphs. Discrete Applied Mathematics, 384, 397–410.
[2] Diego, V., & Fiol, M. A. (2017). Distance mean-regular graphs. Designs, Codes and Cryptography, 84(1–2), 55–71.
[3] Brešar, B., Gastineau, N., Klavžar, S., & Togni, O. (2019). Exact distance graphs of product graphs. Graphs and Combinatorics, 35(6), 1555–1569.