zbMATH — the first resource for mathematics

Critical groups for complete multipartite graphs and Cartesian products of complete graphs. (English) Zbl 1031.05064
Summary: The critical group of a connected graph is a finite abelian group, whose order is the number of spanning trees in the graph, and which is closely related to the graph Laplacian. Its group structure has been determined for relatively few classes of graphs, e.g., complete graphs and complete bipartite graphs. For complete multipartite graphs \(K_{n_1,\dots ,n_k}\), we describe the critical group structure completely. For Cartesian products of complete graphs \(K_{n_1} \times \cdots \times K_{n_k}\), we generalize results of H. Bai [Linear Algebra Appl. 369, 251-261 (2003)] on the \(k\)-dimensional cube, by bounding the number of invariant factors in the critical group, and describing completely its \(p\)-primary structure for all primes \(p\) that divide none of \(n_1,\dots ,n_k\).

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI
[1] Bai, Lin Alg Appl 369 pp 251– (2003)
[2] Algebraic graph theory, second edition. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1993.
[3] Biggs, Bull London Math Soc 29 pp 641– (1997)
[4] Biggs, J Algebraic Combin 9 pp 25– (1999)
[5] Cori, Eur J Combin 21 pp 447– (2000)
[6] Dhar, Phys Rev Lett 64 pp 1613– (1990)
[7] Dhar, J Phys A 28 pp 805– (1995)
[8] and Abstract algebra. Prentice Hall, Inc., Englewood Cliffs, NJ, 1991.
[9] and Algebraic graph theory, Graduate Texts in Math volume 207, Springer-Verlag, New York, 2001.
[10] Lewis, Discrete Math 197/198 pp 537– (1999)
[11] Lorenzini, Discrete Math 91 pp 277– (1991)
[12] The critical group of a directed graph, ArXiv preprint math.c0/0010241, 2003.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.