Endomorphism and Automorphism Graphs

Midhuna V Ajith, Mainak Ghosh, Aparna Lakshmanan S · 2025

Read Endomorphism and Automorphism Graphs by Midhuna V Ajith, Mainak Ghosh, Aparna Lakshmanan S (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-00759.txt.

Introduction

Three mathematicians define graphs that encode how a group's own symmetries can move its elements around, in a 2025 paper. Each element of a group becomes a vertex. A directed edge runs from one element to another when some endomorphism, a structure-preserving self-map, sends the first to the second. Dropping the arrows gives the endomorphism graph, and restricting to reversible maps gives the automorphism graph. The authors explore these graphs' basic traits, including size, girth, and flatness.

They also sort out for which kinds of groups the graphs come out complete, disconnected, tree-shaped, or two-colored in the bipartite sense. The constructions turn algebraic reachability questions into graph questions. The paper maps a young area where group theory and graph theory trade tools.

Catalog record

CREATORMidhuna V Ajith, Mainak Ghosh, Aparna Lakshmanan S
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE26 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-00759

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Endomorphism and Automorphism Graphs Midhuna V Ajith, Mainak Ghosh, Aparna Lakshmanan S Abstract Let G G be a group. The directed endomorphism graph, Endo → ​ ( G ) \overrightarrow{\mathrm{Endo}}(G)\; of G G is a directed graph with vertex set G G and there is a directed edge from the vertex ‘ a a ’ to the vertex ‘ b \,b ’ ( a ≠ b ) (a\neq b) if and only if there exists an endomorphism on G G mapping a a to b b . The endomorphism graph, Endo ⁡ ( G ) \mathrm{Endo}(G)\; of G G is the corresponding undirected simple graph. The automorphism graph, A ​ u ​ t ​ o ​ ( G ) {Auto}(G) of G G is an undirected graph with vertex set G G and there is an edge from the vertex ‘ a a ’ to the vertex ‘ b \,b ’ ( a ≠ b ) (a\neq b) if and only if there exists an automorphism on G G mapping a a to b b . We have explored graph theoretic properties like size, planarity, girth etc. and tried finding out for which types of groups these graphs are complete, diconnected, trees, bipartite and so on. AMS Subject Classification: 05C20, 05C25, 08A35 1 Introduction Algebraic graph theory deals with the study of the interrelationship between algebraic structures and graph theory. Graphs defined on algebraic structures have been an important research area for quite some time. Among various graphs defined on algebraic structures, the most well known is the Cayley graph, which was considered for finite groups by Arthur Cayley in 1878 [ 1 ] . Other such graphs include the commuting graph [ 12 ] , the generating graph [ 9 ] , the directed [ 2 ] as well as the undirected power graph [ 4 ] and the cyclic graph [ 8 ] . We have defined such a graph, termed as endomorphism graph, were there is an edge between two elements of an algebraic structure if there is an endomorphism mapping one of them to the other. Proceeding further, we also defined the automorphism graph of a group. Throughout this paper G represents a group and `e ’ is the identity element of the group. All groups considered in this paper are finite, unless otherwise specified. The order of an element in a group is denoted by |a| , while (a,b) refers to gcd(a,b) . A homomorphism of a group to itself is called an endomorphism , while a one-one, onto endomorphism is an automorphism . The set of all automorphisms of a group again forms a group, called the automorphism group. If f is a homomorphism mapping a to b , then |b| divides |a| . If f is an automorphism mapping a to b , then |a|=|b| . A subgroup N of G is normal if gNg^{-1}\subseteq N,\;\text{for all}\;g\in G . A simple group is a nontrivial group whose only normal subgroups are the trivial group and the group itself. The center Z(G) of a group G is the collection of elements that commute with all elements of the group. The centralizer of an element a , C(a) is the set of all elements in the group that commutes with a . The index of a subgroup H in group G is the number of left or right cosets of H in G , denoted by |G:H| . Let \mathcal{G} denote an undirected graph with vertex set V(\mathcal{G}) . For a,b\in V(\mathcal{G}) , a\sim b indicates that a and b are adjacent in a graph. A component is a maximal connected subgraph of the graph. A simple graph \mathcal{G} is complete if every pair of distinct vertices of \mathcal{G} are adjacent in \mathcal{G} . A clique is a complete subgraph of \mathcal{G} . The girth, g(\mathcal{G}) is the length of the shortest cycle contained in the graph. A graph \mathcal{G} is planar if and only if there exists a drawing of \mathcal{G} in the plane in which no two edges intersect at a point other than a vertex of \mathcal{G} . Equivalently, a graph is planar if and only if it has no subgraph homeomorphic to K_{5} or K_{3,3} . Two simple graphs \mathcal{G}_{1} and \mathcal{G}_{2} are isomorphic if there exists a bijection \psi:V(\mathcal{G}_{1})\rightarrow V(\mathcal{G}_{2}) such that uv is an edge in \mathcal{G}_{1}\;\text{if and only if}\;\psi(u)\psi(v) is an edge in \mathcal{G}_{2} . A graph is bipartite if the vertex set can be partitioned into two non-empty subsets such that each edge have one end in the first set and the other end in the next set. A simple bipartite graph is complete bipartite if every vertex in the first subset is adjacent to all the vertices in the second subset. Let \overrightarrow{\mathcal{G}} denote directed graph or a digraph. A vertex v is reachable from a vertex u in \overrightarrow{\mathcal{G}} if there is a directed path from u to v . A directed graph is diconnected if every vertex of \overrightarrow{\mathcal{G}} is reachable from every other vertex. A Hamiltonian cycle in a directed graph is a spanning cycle. A digraph is Hamiltonian if it contains a Hamiltonian cycle. A point basis of a digraph is a minimal collection of points or vertices from which all other points are reachable. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction). In the directed power graph, \overrightarrow{\mathrm{Pow}}(G) of a group, there is a directed arc from a vertex x to y \iff y=x^{m} for some m\in\mathbb{N} . The undirected power graph, \mathrm{Pow}(G) is the underlying simple graph of \overrightarrow{\mathrm{Pow}}(G) . We studied directed and undirected endomorphism graphs separately, analyzing the types of groups for which these graphs are diconnected, complete, tree or planar. While isomorphic groups have isomorphic directed endomorphism graphs, the converse does not hold for undirected graphs. In the next section, we examine the properties of groups when the identity element is removed from the graph. The paper concludes with a brief discussion on the automorphism graph. 2 Directed and Undirected Endomorphism Graphs Definition 2.1 . The directed endomorphism graph , \overrightarrow{\mathrm{Endo}}(G)\; of G is a directed graph with vertex set G and there is a directed edge from the vertex `a ’ to the vertex `b ’ (a\neq b) if and only if there exists an endomorphism on G mapping a to b . The endomorphism graph , \mathrm{Endo}(G)\; of G is the corresponding undirected simple graph. Note that, there is a possibility for multiple arcs and edges in both the graphs defined above. But here we are considering only simple graphs. Example 2.2 . Consider the group G=\mathbb{Z}_{6} under addition +_{6} . There are 6 endomorphisms on G . Fix a `k ’ between 0 and 5 f_{k}(i)=ki,\;\forall i\in\mathbb{Z}_{6} denotes an endomorphism on \mathbb{Z}_{6} . Figure 1 : \overrightarrow{\mathrm{Endo}}(\mathbb{Z}_{6}) and \text{Endo}(\mathbb{Z}_{6}) Theorem 2.3 . The directed endomorphism graphs (and hence the endomorphism graphs) of isomorphic groups are isomorphic. The converse is not true for endomorphism graphs. Proof. Consider two isomorphic groups, G_{1} and G_{2} . Let \phi:G_{1}\rightarrow G_{2} be an isomorphism with \phi(a_{1})=a_{2} and \phi(b_{1})=b_{2} for some a_{1},b_{1}\in

Read the complete text