×

When is the Cayley graph of a semigroup isomorphic to the Cayley graph of a group. (English) Zbl 1399.05107

This article shows that all vertex-transitive, connected and undirected finite Cayley graphs of semigroups are isomorphic to Cayley graphs of groups, and all finite vertex-transitive Cayley graphs of inverse semigroups are isomorphic to Cayley graphs of groups. The paper contains several related open problems.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fan, S. H.—Zeng, Y. S.: On Cayley graphs of bands, Semigroup Forum 74 (2007), 99-105. · Zbl 1125.05051
[2] Howie, J. M.: An Introduction to Semigroup Theory, Academic Press, London, 1976. · Zbl 0355.20056
[3] Jiang, Z. H.: An answer to a question of Kelarev and Praeger on Cayley graphs of semigroups, Semigroup Forum 69 (2004), 457-461. · Zbl 1065.20069
[4] Kelarev, A. V.—Quinn, S. J.: Directed graphs and combinatorial properties of semigroups, J. Algebra 251 (2002), 16-26. · Zbl 1005.20043
[5] Kelarev, A. V.: On undirected Cayley graphs, Australas. J. Combin. 25 (2002), 73-78. · Zbl 0993.05085
[6] Kelarev, A. V.: Graph Algebras and Automata, Marcel Dekker, Inc., New York, 2003. · Zbl 1070.68097
[7] Kelarev, A. V.—Praeger, C. E.: On transitive Cayley graphs of groups and semigroups, European J. Combin. 24 (2003), 59-72. · Zbl 1011.05027
[8] Kelarev, A. V.—Quinn, S. J.: A combinatorial property and Cayley graphs of semigroups, Semigroup Forum 66 (2003), 89-96. · Zbl 1016.20047
[9] Kelarev, A. V.: Labelled Cayley graphs and minimal automata, Australas. J. Combin. 30 (2004), 95-101. · Zbl 1152.68482
[10] Kelarev, A.V.: On Cayley graphs of inverse semigroups, Semigroup Forum 72 (2006), 411-418. · Zbl 1107.20057
[11] Kelarev, A. V.—Ryan, J.—Yearwood, J.: Cayley graphs as classifiers for data mining: the influence of asymmetries, Discrete Math. 309 (2009), 5360-5369. · Zbl 1206.05050
[12] Khosravi, B—Mahmoudi, M.: On Cayley graphs of rectangular groups, Discrete Math. 310 (2010), 804-811. · Zbl 1208.05048
[13] Khosravi, B.—Khosravi, B.: On Cayley graphs of semilattices of semigroups, Semigroup Forum 86 (2013), 114-132. · Zbl 1268.20064
[14] Khosravi, B.—Khosravi, B.: On combinatorial properties of bands, Comm. Algebra 42 (2014), 1379-1395. · Zbl 1286.05069
[15] Khosravi, B.—Khosravi, B.—Khosravi, B.: On color-automorphism vertex transitivity of semigroups, European J. Combin. 40 (2014), 55-64. · Zbl 1297.05110
[16] Knauer, U.: Algebraic Graph Theory. Morphisms, Monoids and Matrices, De Gruyter, Berlin and Boston, 2011. · Zbl 1338.05001
[17] Knauer, K.—Knauer, U.: On planar right groups, Semigroup Forum 92 (2016), 142-157. · Zbl 1353.20043
[18] Panma, S.—Na Chiangmai, N.—Knauer, U.—Arworn, S.: Characterizations of Clifford semigroup digraphs, Discrete Math. 306 (2006), 1247-1252. · Zbl 1096.05045
[19] Panma, S.N.—Knauer, U.—Arworn, S.: On transitive Cayley graphs of strong semilattices of right (left) groups, Discrete Math. 309 (2009), 5393-5403. · Zbl 1198.05095
[20] Sabidussi, G.: On a class of fixed-point-free graphs, Proc. Amer. Math. Soc. 9 (1958), 800-804. · Zbl 0091.37701
[21] Wang, S. F.—Zhang, D: A classification of vertex-transitive Cayley digraphs of strong semilattices of completely simple semigroups, Math. Slovaca 62 (2012), 829-840. · Zbl 1313.05174
[22] Wang, S. F.—Li, Y. H.: On Cayley graphs of completely 0-simple semigroups, Cent. Eur. J. Math. 11 (2013), 924-930. · Zbl 1267.05142
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.