Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

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

 
 

 

Group-theoretic generalisations of vertex and edge connectivities


Authors: Yinan Li and Youming Qiao
Journal: Proc. Amer. Math. Soc. 148 (2020), 4679-4693
MSC (2010): Primary 20D15, 05C40, 15A69
DOI: https://doi.org/10.1090/proc/15184
Published electronically: August 14, 2020
MathSciNet review: 4143386
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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) $ \vert S/[S,S]\vert=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.


References [Enhancements On Off] (What's this?)


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


Additional Information

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

DOI: https://doi.org/10.1090/proc/15184
Keywords: $p$-groups of class $2$, graph connectivity, matrix spaces, bilinear maps
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
Article copyright: © Copyright 2020 American Mathematical Society