×

Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields. (English) Zbl 1303.05083

Summary: A maximal minor \(M\) of the Laplacian of an \(n\)-vertex Eulerian digraph \(\Gamma\) gives rise to a finite group \(\mathbb{Z}^{n-1}/\mathbb{Z}^{n-1} M\) known as the sandpile (or critical) group \(S(\Gamma)\) of \(\Gamma\). We determine \(S(\Gamma)\) of the generalized de Bruijn graphs \(\Gamma = \mathrm{DB}(n, d)\) with vertices \(0, \ldots, n-1\) and arcs \((i, d i + k)\) for \(0 \leq i \leq n-1\) and \(0 \leq k \leq d-1\), and closely related generalized Kautz graphs, extending and completing earlier results for the classical de Bruijn and Kautz graphs. Moreover, for a prime \(p\) and an \(n\)-cycle permutation matrix \(X \in \mathrm{GL}_n(p)\) we show that \(S(\mathrm{DB}(n, p))\) is isomorphic to the quotient by \(\langle X \rangle\) of the centralizer of \(X\) in \(\mathrm{PGL}_n(p)\). This offers an explanation for the coincidence of numerical data in sequences A027362 and A003473 of the OEIS, and allows one to speculate upon a possibility to construct normal bases in the finite field \(\mathbb{F}_{p^n}\) from spanning trees in \(\mathrm{DB}(n, p)\).

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C20 Directed graphs (digraphs), tournaments
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C35 Extremal problems in graph theory

Software:

SageMath; OEIS; hfloat; FXT
PDFBibTeX XMLCite
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Generalized Euler phi function (for p=2).

References:

[1] Alfaro, C. A.; Valencia, C. E., On the sandpile group of the cone of a graph, Linear Algebra Appl., 436, 5, 1154-1176 (2012) · Zbl 1236.05131
[2] Arndt, J., Matters Computational: Ideas, Algorithms, Source Code (2010), Springer · Zbl 1210.68128
[3] Bass, H., Algebraic K-Theory (1968), W.A. Benjamin, Inc.: W.A. Benjamin, Inc. New York-Amsterdam · Zbl 0174.30302
[4] Bidkhori, H.; Kishore, S., A bijective proof of a theorem of Knuth, Combin. Probab. Comput., 20, 1, 11-25 (2010) · Zbl 1221.05174
[5] Biggs, N., Chip-firing and the critical group of a graph, J. Algebraic Combin., 9, 25-45 (1999) · Zbl 0919.05027
[6] Chan, S. H., Relations between sandpiles of some graphs and other combinatorial objects (2012), School of Physical and Mathematical Sciences, Nanyang Technological University: School of Physical and Mathematical Sciences, Nanyang Technological University Singapore, Final year project thesis
[7] Chan, S. H.; Hollmann, H.; Pasechnik, D. V., Circulant matrices and sandpile groups of generalized de Bruijn graphs, (Nešetřil, J.; Pellegrini, M., Proceedings of EuroComb 2013. Proceedings of EuroComb 2013, Publications of the Scuola Normale Superiore, vol. 16 (2013), Springer)
[8] Chen, P.; Hou, Y., On the sandpile group of \(P_4 \times C_n\), European J. Combin., 29, 2, 532-534 (2008) · Zbl 1132.05029
[9] Chen, P.; Hou, Y.; Woo, C., On the critical group of the Möbius ladder graph, Australas. J. Combin., 36, 133-142 (October 2006)
[10] Dartois, A.; Fiorenzi, F.; Francini, P., Sandpile group on the graph \(D_n\) of the dihedral group, European J. Combin., 24, 7, 815-824 (2003) · Zbl 1026.05055
[11] Du, D.-Z.; Cao, F.; Hsu, D. F., De Bruijn digraphs, Kautz digraphs, and their generalizations, (Du, D.-Z.; Hsu, D. F., Combinatorial Network Theory (1996), Kluwer Academic), 65-105 · Zbl 0845.05049
[12] Du, D.-Z.; Hsu, D.; Peck, G., Connectivity of consecutive-\(d\) digraphs, Discrete Appl. Math., 37, 38, 169-177 (1992) · Zbl 0776.05045
[13] Du, D. Z.; Hwang, F. K., Generalized de Bruijn digraphs, Networks, 18, 27-38 (1988) · Zbl 0654.05036
[14] Duzhin, S. V.; Pasechnik, D. V., Automorphisms of necklaces and sandpile groups (2013) · Zbl 1308.05058
[15] Holroyd, A. E.; Levine, L.; Mészáros, K.; Peres, Y.; Propp, J.; Wilson, D. B., Chip-firing and rotor-routing on directed graphs, (In and Out of Equilibrium. 2. In and Out of Equilibrium. 2, Progr. Probab., vol. 60 (2008), Birkhäuser: Birkhäuser Basel), 331-364 · Zbl 1173.82339
[16] Hou, Y.; Woo, C.; Chen, P., On the sandpile group of the square cycle \(C_n^2\), Linear Algebra Appl., 418, 457-467 (2006) · Zbl 1108.05062
[17] Imase, M.; Itoh, M., Design to minimize diameter on building-block network, IEEE Trans. Comput., C-30, 6, 439-442 (June 1981)
[18] Imase, M.; Itoh, M., A design for directed graphs with minimum diameter, IEEE Trans. Comput., C-32, 8, 782-784 (Aug. 1983)
[19] Levine, L., Sandpile groups and spanning trees of directed line graphs, J. Combin. Theory Ser. A, 118, 2, 350-364 (2011) · Zbl 1292.05135
[20] Lidl, R.; Niederreiter, H., Finite Fields, Encyclopedia of Mathematics and Its Applications, vol. 20 (1997), Cambridge University Press: Cambridge University Press Cambridge, With a foreword by P.M. Cohn
[21] Lorenzini, D. J., A finite group attached to the laplacian of a graph, Discrete Math., 91, 277-282 (1991) · Zbl 0755.05079
[22] Merris, R., Unimodular equivalence of graphs, Linear Algebra Appl., 173, 181-189 (Aug. 1992)
[23] Newman, M., Integral Matrices, Pure and Applied Mathematics, vol. 45 (1972), Academic Press · Zbl 0254.15009
[25] Perkinson, D., Sage sandpiles (2012)
[26] Raza, Z., On the critical group of \(\hat{W}_{3 n} \), (Proceedings of the 2011 International Conference on Applied & Computational Mathematics. Proceedings of the 2011 International Conference on Applied & Computational Mathematics, ICACM’11, Stevens Point, Wisconsin, USA (2011), World Scientific and Engineering Academy and Society (WSEAS)), 98-106
[27] Raza, Z.; Waheed, S. A., On the critical group of \(\hat{W}_{4 n} \), J. Appl. Math. Inform., 30, 993-1003 (2012) · Zbl 1251.05035
[28] Reutenauer, C., Free Lie Algebras (1993), Oxford University Press · Zbl 0798.17001
[29] Rushanan, J. J., Topics in integral matrices and abelian group codes (1986), California Institute of Technology, PhD thesis
[30] Shen, J.; Hou, Y., On the sandpile group of \(3 \times n\) twisted bracelets, Linear Algebra Appl., 429, 8-9, 1894-1904 (Oct. 2008)
[31] Stein, W., Sage mathematics software (Version 5.7). The Sage Development Team (2012)
[32] van Aardenne-Ehrenfest, T.; de Bruijn, N. G., Circuits and trees in oriented linear graphs, Simon Stevin, 28, 203-217 (1951) · Zbl 0044.38201
[33] Wagner, D., The critical group of a directed graph (2000), Available at
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.