On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions

DOI10.1016/J.EJC.2021.103404MaRDI QIDQ1979440zbMATH OpenOpenAlexFDO

Authors Xiaoyu He, Youming Qiao

Publication date 2 September 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.07200

zbMATH Keywords

graph homomorphismsgroup isomorphismMekler's construction

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Group actions on combinatorial structures (05E18) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Finite nilpotent groups, (p)-groups (20D15)

Abstract: Let $p$ be an odd prime. From a simple undirected graph $G$, through the classical procedures of Baer (Trans. Am. Math. Soc., 1938), Tutte (J. Lond. Math. Soc., 1947) and Lov'asz (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 first result is to show that this construction of groups from graphs respects isomorphism types. That is, given two graphs $G$ and $H$, $G$ and $H$ are isomorphic as graphs if and only if $P_G$ and $P_H$ are isomorphic as groups. Our second contribution is a new homomorphism notion for graphs. Based on this notion, a category of graphs can be defined, and the Baer-Lov'asz-Tutte construction naturally leads to a functor from this category of graphs to the category of groups.

Recommendations

• Isomorphisms of Graph Groups
• scientific article; zbMATH DE number 4021431
• scientific article; zbMATH DE number 2185572
• Group-theoretic generalisations of vertex and edge connectivities
• Simple graphs containing induced subgraphs whose automorphism groups are isomorphic to subgroups of a given finite group

Cites work

• Decomposing \(p\)-groups via Jordan algebras.
• From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces
• Graph isomorphism in quasipolynomial time (extended abstract)
• Group-theoretic generalisations of vertex and edge connectivities
• Groups with Abelian Central Quotient Group
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 475362 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 7359884 (Why is no real title available?)
• Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice
• Mekler's construction and generalized stability
• On the automorphism groups of strongly regular graphs. I
• Singular spaces of matrices and their application in combinatorics
• Stability of nilpotent groups of class 2 and prime exponent
• The asymptotic spectrum of graphs and the Shannon capacity
• The asymptotic spectrum of tensors.
• The Factorization of Linear Graphs
• The occurrence of finite groups in the automorphism group of nilpotent groups of class 2

Cited in

(7)

• Enumerating conjugacy classes of graphical groups over finite fields
• Connections between graphs and matrix spaces
• Count-free Weisfeiler-Leman and group isomorphism
• On the descriptive complexity of groups without abelian normal subgroups
• On the parallel complexity of group isomorphism via Weisfeiler-Leman
• On the complexity of isomorphism problems for tensors, groups, and polynomials III: actions by classical groups
• On the descriptive complexity of groups without abelian normal subgroups (extended abstract)

This page was built for publication: On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1979440)