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

2020/03/16 by Xiaoyu He, He, Xiaoyu, Youming Qiao +1 · 1 citation
Mathematics · #05C60 #20D15 #20J15 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Geometric and Algebraic Topology #Group Theory (math.GR) #Homotopy and Cohomology in Algebraic Topology

paper · pdf · doi:10.48550/arxiv.2003.07200

openalex publication_date 2020/03/16 · openalex created_date 2020/03/23 · openalex updated_date 2026/07/28

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á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 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ász-Tutte construction naturally leads to a functor from this category of graphs to the category of groups.

Citations

• The Factorization of Linear Graphs
• Graph Isomorphism in Quasipolynomial Time

Cited by

• On the Parallel Complexity of Identifying Groups and Quasigroups via Decompositions

Related

• Automorphism groups of graphs
• On the BCI Problem
• Constructions of graphs with any possible two-fold automorphism and automorphism groups
• Automorphism groups of a graph and a vertex-deleted subgraph
• Reduction of the group isomorphism problem to the group automorphism problem