Group-theoretic generalisations of vertex and edge connectivities

Abstract:

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^n$. We define two parameters for $P$ related to central decompositions. The first parameter, $\kappa (P)$, is the smallest integer $s$ for the existence of a subgroup $S$ of $P$ satisfying (1) $S\cap [P,P]=[S,S]$, (2) $|S/[S,S]|=p^{n-s}$, and (3) $S$ is centrally decomposable. The second parameter, $\lambda (P)$, is the smallest integer $s$ for the existence of a central subgroup $N$ of order $p^s$, 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_G$ of class $2$ and exponent $p$ that is naturally associated with $G$. Our main results show that the vertex connectivity $\kappa (G)$ equals $\kappa (P_G)$, and the edge connectivity $\lambda (G)$ equals $\lambda (P_G)$.

We also discuss the relation between $\kappa (P)$ and $\lambda (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.