Group-theoretic generalisations of vertex and edge connectivities

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.

• View at Publisher

Free Full Text ( Final Version , 347kb )