The Isomorphism Problem for Cayley Graphs on Monogenic Semigroups
math.CO
Submitted: 2026-11-10
Updated: 2026-11-10
Comments: 22 pages, 5 figures
License: http://creativecommons.org/licenses/by/4.0/
The gist: In this paper, we investigate the structural properties of Cayley graphs of monogenic semigroups and present a complete characterization of their weakly connected components.
Terminology
Abstract
In this paper, we investigate the structural properties of Cayley graphs of monogenic semigroups and present a complete characterization of their weakly connected components. Several essential properties of these components are rigorously proven. Building upon these structural results, we introduce the notion of labelled colour-permuting isomorphisms between Cayley graphs. Using this new isomorphism framework, we address the Cayley graph isomorphism problem for monogenic semigroups, commonly known as the CI problem. In particular, we establish the necessary and sufficient conditions under which two Cayley graphs over monogenic semigroups are labelled colour-permuting isomorphic.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality