zbMATH — the first resource for mathematics

The critical group of a line graph. (English) Zbl 1256.05095
Summary: The critical group of a graph is a finite abelian group whose order is the number of spanning forests of the graph. This paper provides three basic structural results on the critical group of a line graph.
The first deals with connected graphs containing no cut-edge. Here the number of independent cycles in the graph, which is known to bound the number of generators for the critical group of the graph, is shown also to bound the number of generators for the critical group of its line graph.
The second gives, for each prime \(p\), a constraint on the \(p\)-primary structure of the critical group, based on the largest power of \(p\) dividing all sums of degrees of two adjacent vertices.
The third deals with connected graphs whose line graph is regular. Here known results relating the number of spanning trees of the graph and of its line graph are sharpened to exact sequences which relate their critical groups.
The first two results interact extremely well with the third. For example, they imply that in a regular nonbipartite graph, the critical group of the graph and that of its line graph determine each other uniquely in a simple fashion.

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C05 Trees
05C76 Graph operations (line graphs, products, etc.)
05E99 Algebraic combinatorics
Full Text: DOI arXiv
[1] Bacher R., de la Harpe P., Nagnibeda T.: The lattice of integral flows and the lattice of integral cuts on a finite graph. Bull. Soc. Math. France 125(2), 167–198 (1997) · Zbl 0891.05062
[2] Bai H.: On the critical group of the n-cube. Linear Algebra Appl. 369, 251–261 (2003) · Zbl 1023.05096 · doi:10.1016/S0024-3795(02)00727-9
[3] Berget, A.: Critical groups of some regular line graphs. Available online at http://www.math.ucdavis.edu/\(\sim\)berget/research/ (2003)
[4] Biggs N.: Algebraic potential theory on graphs. Bull. London Math. Soc. 29(6), 641–682 (1997) · Zbl 0892.05033 · doi:10.1112/S0024609397003305
[5] Biggs N.: Algebraic Graph Theory, 2nd Ed. Cambridge University Press, Cambridge (1993) · Zbl 0805.68094
[6] Cori R., Rossin D.: On the sandpile group of dual graphs. European J. Combin. 21(4), 447–459 (2000) · Zbl 0969.05034 · doi:10.1006/eujc.1999.0366
[7] Cvetković D., Doob M., Sachs H.: Spectra of Graphs. Academic Press, Inc. (1980) · Zbl 0458.05042
[8] Godsil C., Royle G.: Algebraic Graph Theory. Springer-Verlag, New York (2001) · Zbl 0968.05002
[9] Hartsfield N., Ringel G.: Pearls in Graph Theory: A Comprehensive Introduction. Academic Press, Boston, MA (1994) · Zbl 0823.05001
[10] Jacobson B., Neidermeier A., Reiner V.: Critical groups for complete multipartite graphs and Cartesian products of complete graphs. J. Graph Theory 44(3), 231–250 (2003) · Zbl 1031.05064 · doi:10.1002/jgt.10139
[11] Kelmans, A.K.: On properties of the characteristic polynomial of a graph. In: Kibernetiku –Na Sluzbu Kom. (in Russian), Vol. 4, pp. 27–47. Gosenergoizdat, Moscow, (1967)
[12] Levine L.: Sandpile groups and spannings trees of directed line graphs. J. Combin. Theory Ser. A 118(2), 350–364 (2011) · Zbl 1292.05135 · doi:10.1016/j.jcta.2010.04.001
[13] Lorenzini D.: A finite group attached to the laplacian of a graph. Discrete Math. 91(3), 277–282 (1991) · Zbl 0755.05079 · doi:10.1016/0012-365X(90)90236-B
[14] Macdonald I.G.: Symmetric Functions and Hall Polynomials, 2nd Ed. Clarendon Press, New York (1995) · Zbl 0824.05059
[15] Mohar B. et al.: The Laplacian spectrum of graphs. In: Alavi, Y. (eds) Graph Theory, Combinatorics, and Applications, Vol. 2., pp. 871–898. Wiley, New York (1991) · Zbl 0840.05059
[16] Rubey, M.: Counting Spanning Trees. Diplomarbeit, Universität Wien (2000)
[17] Stanley R.P.: Enumerative Combinatorics, Vol. 2. Cambridge University Press, Cambridge (1999) · Zbl 0928.05001
[18] Stanley, R.P.: A zonotope associated with graphical degree sequences. In: Gritzmann, P., Sturmfels, B. (eds.) Applied Geometry and Discrete Mathematics, pp. 555–570. Amer. Math. Soc., Providence, RI (1991) · Zbl 0737.05057
[19] Treumann, D.: Functoriality of critical groups. Bachelor’s thesis, Univ. of Minnesota. Available online at http://www.math.umn.edu/\(\sim\)reiner/REU/REU.html (2002)
[20] Vahovskii E.B.: On the characteristic numbers of incidence matrices for non-singular graphs. Sibirsk. Mat. Zh. 6, 44–49 (1965) (in Russian)
[21] West D.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River, NJ (2001) · Zbl 0992.83079
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.