Inverse monoids of partial graph automorphisms
- PDF / 492,865 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 67 Downloads / 195 Views
Inverse monoids of partial graph automorphisms Robert Jajcay1,2
· Tatiana Jajcayová1 · Nóra Szakács3 · Mária B. Szendrei3
Received: 13 September 2018 / Accepted: 29 January 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract A partial automorphism of a finite graph is an isomorphism between its vertex-induced subgraphs. The set of all partial automorphisms of a given finite graph forms an inverse monoid under composition (of partial maps). We describe the algebraic structure of such inverse monoids by the means of standard tools of inverse semigroup theory, namely Green’s relations and some properties of the natural partial order, and give a characterization of inverse monoids which arise as inverse monoids of partial graph automorphisms. We extend our results to digraphs and edge-colored digraphs as well.
1 Introduction The study of almost any type of combinatorial structures includes problems of distinguishing different objects via the use of isomorphisms and, more specifically, leads to questions concerning the automorphism groups of the structures under consideration. The problem of determining the automorphism group for a specific combinatorial
The first author was partially supported by VEGA 1/0474/15, VEGA 1/0596/17, VEGA 1/0423/20, APVV-15-0220, and by the Slovenian Research Agency (research projects N1-0038, N1-0062, J1-9108). The second author was partially supported by VEGA 1/0039/17 and VEGA 1/0719/18. The third and fourth authors were partially supported by the National Research, Development and Innovation Office, grants no. K104251 and K115518.
B
Robert Jajcay [email protected] Tatiana Jajcayová [email protected] Nóra Szakács [email protected] Mária B. Szendrei [email protected]
1
Comenius University, Bratislava, Slovakia
2
University of Primorska, Koper, Slovenia
3
Bolyai Institute, University of Szeged, Aradi vértanúk tere 1., Szeged H-6720, Hungary
123
Journal of Algebraic Combinatorics
structure or a class of combinatorial structures is a notoriously hard computational task whose exact complexity is the subject of intense research efforts. For example, the time complexity of determining the automorphism group of a finite graph (as a function of its order) has been the focus of a series of recent highly publicized lectures of Babai [1]. Knowledge of the automorphism group of a specific combinatorial object allows one to make various claims about its structure. As an extreme example, the fact that the induced action of the automorphism group of a graph on the set of unordered pairs of its vertices is transitive yields immediately that the graph under consideration is n . Similarly, vertex transitivity of either the complete graph K n or its complement K the action of the automorphism group of a graph yields that each vertex of the graph is contained in the same number of cycles of prescribed length (e.g., [5]). However, the usefulness of knowing the automorphism group of a graph decreases with an increasing nu
Data Loading...
