Let p be an odd prime. Let P be a finite p-group of class 2 and exponent p, whose commutator quotient P/[P, P] is of order pn. We define two parameters for P related to central decompositions. The first parameter, κ(P), is the smallest integer s for the existence of a subgroup S of P satisfying (1) S ∩ [P, P] = [S, S], (2) |S/[S, S]| = pn−s, and (3) S is centrally decomposable. The second parameter, λ(P), is the smallest integer s for the existence of a central subgroup N of order ps, such that P/N is centrally decomposable. While defined in purely group-theoretic terms, these two parameters generalise, respectively, the vertex and edge connectivities of graphs: For a simple undirected graph G, through the classical procedures of Baer (Trans. Amer. Math. Soc., 1938), Tutte (J. Lond. Math. Soc., 1947) and Lovász (B. Braz. Math. Soc., 1989), there is a p-group PG of class 2 and exponent p that is naturally associated with G. Our main results show that the vertex connectivity κ(G) equals κ(PG), and the edge connectivity λ(G) equals λ(PG). We also discuss the relation between κ(P) and λ(P) for a general p-group P of class 2 and exponent p, as well as the computational aspects of these parameters. In particular, our main results imply that the p-group central decomposition algorithm of Wilson (J. Algebra and J. of Group Theory, 2009) can be used to solve the graph connectivity problem.

, , ,
doi.org/10.1090/proc/15184
Proceedings of the American Mathematical Society
Progress in quantum computing:Algorithms, communication, and applications
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Li, Y, & Qiao, Y. (2020). Group-theoretic generalisations of vertex and edge connectivities. Proceedings of the American Mathematical Society, 148(11), 4679–4693. doi:10.1090/proc/15184