20201101
Grouptheoretic generalisations of vertex and edge connectivities
Publication
Publication
Proceedings of the American Mathematical Society , Volume 148  Issue 11 p. 4679 4693
Let p be an odd prime. Let P be a finite pgroup 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 grouptheoretic 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 pgroup 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 pgroup P of class 2 and exponent p, as well as the computational aspects of these parameters. In particular, our main results imply that the pgroup central decomposition algorithm of Wilson (J. Algebra and J. of Group Theory, 2009) can be used to solve the graph connectivity problem.
Additional Metadata  

, , ,  
doi.org/10.1090/proc/15184  
Proceedings of the American Mathematical Society  
Progress in quantum computing:Algorithms, communication, and applications  
Organisation  Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands 
Li, Y, & Qiao, Y. (2020). Grouptheoretic generalisations of vertex and edge connectivities. Proceedings of the American Mathematical Society, 148(11), 4679–4693. doi:10.1090/proc/15184
