# Proceedings of the American Mathematical Society

Published by the American Mathematical Society, the Proceedings of the American Mathematical Society (PROC) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6826 (online) ISSN 0002-9939 (print)

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

## Group-theoretic generalisations of vertex and edge connectivitiesHTML articles powered by AMS MathViewer

by Yinan Li and Youming Qiao
Proc. Amer. Math. Soc. 148 (2020), 4679-4693 Request permission

## 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.

Similar Articles
• Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 20D15, 05C40, 15A69
• Retrieve articles in all journals with MSC (2010): 20D15, 05C40, 15A69
• Yinan Li
• Affiliation: Centrum Wiskunde and Informatica and QuSoft, Science Park 123, 1098XG Amsterdam, Netherlands
• MR Author ID: 1240769
• ORCID: 0000-0002-5456-1319
• Email: Yinan.Li@cwi.nl
• Youming Qiao
• Affiliation: Center for Quantum Software and Information, University of Technology, Sydney, Ultimo NSW 2007, Australia
• MR Author ID: 938330
• ORCID: 0000-0003-4334-1449
• Email: Youming.Qiao@uts.edu.au
• Received by editor(s): October 30, 2019
• Received by editor(s) in revised form: March 24, 2020
• Published electronically: August 14, 2020
• Additional Notes: The first author was partially supported by ERC Consolidator Grant 615307-QPROGRESS.
The second author was partially supported by the Australian Research Council DP200100950.
• Communicated by: Martin Liebeck