Inverse monoids of partial graph automorphisms

DOI10.1007/S10801-020-00944-5MaRDI QIDQ2038891zbMATH OpenOpenAlexFDO

Authors Nóra Szakács, Robert Jajcay, Tatiana Baginová Jajcayová, Mária B. Szendrei

Publication date 7 July 2021

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

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

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

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 the 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.

Recommendations

• Inverse semigroups with certain types of partial automorphism monoids
• scientific article; zbMATH DE number 3897234
• Inverse monoids of graphs
• Inverse semigroups of partial automaton permutations.
• Frucht theorem for inverse semigroups

Cites work

• A congruence theorem for trees
• Cayley color graphs of inverse semigroups and groupoids
• Constructing graphs with pairs of pseudo-similar vertices
• Constructing graphs with several pseudosimilar vertices or edges
• Frucht theorem for inverse semigroups
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph reconstruction by permutations
• Graphs and their associated inverse semigroups
• Graphs with three mutually pseudo-similar vertices
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 3747160 (Why is no real title available?)
• scientific article; zbMATH DE number 3790470 (Why is no real title available?)
• scientific article; zbMATH DE number 1761434 (Why is no real title available?)
• scientific article; zbMATH DE number 951516 (Why is no real title available?)
• scientific article; zbMATH DE number 1409202 (Why is no real title available?)
• scientific article; zbMATH DE number 5488086 (Why is no real title available?)
• Large sets of pseudosimilar vertices
• Lengths of words in transformation semigroups generated by digraphs
• On the excess of vertex-transitive graphs of given degree and girth
• Pseudosimilar vertices in a graph
• Subgraphs as a measure of similarity
• The \(\mathfrak q\)-theory of finite semigroups.

Cited in

(9)

• Frucht theorem for inverse semigroups
• Inverse monoids of graphs
• Partial automorphisms and injective partial endomorphisms of a finite undirected path
• Inverse automata and inverse monoid: Schützenberger-graphs of a semilattice with identity.
• scientific article; zbMATH DE number 3897234 (Why is no real title available?)
• On one class of factorizable fundamental inverse monoids.
• FREE INVERSE MONOIDS AND GRAPH IMMERSIONS
• Classification of finite structurally uniform nilsemigroups
• Orbit closed permutation groups, relation groups, and simple groups

This page was built for publication: Inverse monoids of partial graph automorphisms

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