Group-theoretic generalisations of vertex and edge connectivities
- Publisher:
- AMER MATHEMATICAL SOC
- Publication Type:
- Journal Article
- Citation:
- Proceedings of the American Mathematical Society, 2020, 148, (11), pp. 4679-4693
- Issue Date:
- 2020-11-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
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 p . 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]| = p − , 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 p , 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 P of class 2 and exponent p that is naturally associated with G. Our main results show that the vertex connectivity κ(G) equals κ(P ), and the edge connectivity λ(G) equals λ(P ). 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. n n s s G G G
Please use this identifier to cite or link to this item: