×

On the automorphism groups of vertex-transitive Cayley digraphs of monoids. (English) Zbl 1464.05180

Summary: L. Babai and C. D. Godsil [Eur. J. Comb. 3, 9–15 (1982; Zbl 0483.05033)] conjectured that almost all Cayley digraphs are digraphical regular representations. M. Xu [Discrete Math. 182, No. 1–3, 309–319 (1998; Zbl 0887.05025)] conjectured that almost all Cayley digraphs are normal (i.e., \(G_L\) is a normal subgroup of the automorphism group of \(\text{Cay}(G,C)\)). Finally, in 1994, Praeger and Mckay conjectured that almost all undirected vertex-transitive graphs are Cayley graphs of groups. In this paper, first we present the variants of these conjectures for Cayley digraphs of monoids and we determine when the variant of Babai and Godsil’s conjecture [loc. cit.] is equivalent to the variant of Xu’s conjecture. Then, as a special consequence of our results, we conclude that Xu’s conjecture [loc. cit.] is equivalent to Babai and Godsil’s conjecture. On the other hand, we give affirmative answer to the variant of Praeger and Mckay’s conjecture and we prove that a Cayley digraph of a monoid is vertex-transitive if and only if it is isomorphic to a Cayley digraph of a group. Finally, we use this characterization to give an affirmative answer to a question raised by A. V. Kelarev and C. E. Praeger [Eur. J. Comb. 24, No. 1, 59–72 (2003; Zbl 1011.05027)] about vertex-transitivity of Cayley digraphs of monoids. Also using this characterization, we explicitly determine the automorphism groups of vertex-transitive Cayley digraphs of monoids.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C20 Directed graphs (digraphs), tournaments
05C62 Graph representations (geometric and intersection representations, etc.)
06A15 Galois correspondences, closure operators (in relation to ordered sets)
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Babai, L.: Automorphism groups, isomorphism, reconstruction. Handbook of Combinatorics, Chapter 7 (1994)
[2] Babai, L.; Godsil, C., On the automorphism groups of almost all Cayley graphs, European J. Combin., 3, 9-15 (1982) · Zbl 0483.05033
[3] Burris, S., Sankappanavar, H.P.: A course in universal algebra. Graduate Texts in Mathematics, vol. 78. Springer-Verlag, New York-Berlin (1981) · Zbl 0478.08001
[4] Dobson, E.; Spiga, P.; Verret, G., Cayley graphs on Abelian groups, Combinatorica, 36, 4, 371-393 (2016) · Zbl 1399.05100
[5] Godsil, C., On the full automorphism group of a graph, Combinatorica, 1, 3, 243-256 (1981) · Zbl 0489.05028
[6] Gomes, G.; Howie, JM, On the ranks of certain finite semigroups of transformations, Math. Proc. Cambridge Philos. Soc., 101, 3, 395-403 (1987) · Zbl 0622.20056
[7] Gutik, O.: On the group of automorphisms of the Brandt 0-extension of a monoid with zero. In: The 16th ITAT Conference InformationTechnologies-Applications and Theory (ITAT 2016), Tatranske Matliare, Slovakia pp. 237-240 (2016)
[8] Howie, JM; Ribeiro, MIM, Rank properties in finite semigroups, Comm. Algebra, 27, 11, 5333-5347 (1999) · Zbl 0940.20056
[9] Hujdurovic, A.; Kutnar, K.; Morris, DW; Morris, J., On colour-preserving automorphisms of Cayley graphs, Ars Math. Contemp., 11, 1, 189-213 (2016) · Zbl 1351.05107
[10] Jiang, Z., An answer to a question of Kelarev and Praeger on Cayley graphs of semigroups, Semigroup Forum, 69, 3, 457-461 (2004) · Zbl 1065.20069
[11] Kelarev, AV, Combinatorial properties and homomorphisms of semigroups, Internat. J. Algebra Comput., 4, 3, 443-450 (1994) · Zbl 0815.20054
[12] Kelarev, AV, On undirected Cayley graphs, Australas. J. Combin., 25, 73-78 (2002) · Zbl 0993.05085
[13] Kelarev, AV, Ring Constructions and Applications (2002), River Edge: World Scientific, River Edge · Zbl 0999.16036
[14] Kelarev, AV, Graph Algebras and Automata (2003), New York: Marcel Dekker, New York
[15] Kelarev, AV, Labelled Cayley graphs and minimal automata, Australas. J. Combin., 30, 95-101 (2004) · Zbl 1152.68482
[16] Kelarev, AV; Praeger, CE, On transitive Cayley graphs of groups and semigroups, European J. Combin., 24, 1, 59-72 (2003) · Zbl 1011.05027
[17] Kelarev, AV; Ras, C.; Zhou, S., Distance labellings of Cayley graphs of semigroups, Semigroup Forum, 91, 3, 611-624 (2015) · Zbl 1355.20043
[18] Kelarev, AV; Ryan, J.; Yearwood, JL, Cayley graphs as classifiers for data mining: the influence of asymmetries, Discrete Math., 309, 17, 5360-5369 (2009) · Zbl 1206.05050
[19] Khosravi, B., On Cayley graphs of left groups, Houston J. Math., 35, 3, 745-755 (2009) · Zbl 1194.05110
[20] Khosravi, B., The endomorphism monoids and automorphism groups of Cayley graphs of semigroups, Semigroup Forum, 95, 1, 179-191 (2017) · Zbl 1428.20057
[21] Khosravi, B., On the Cayley graphs of completely simple semigroups, Bull. Malays. Math. Sci. Soc., 41, 2, 741-749 (2018) · Zbl 1390.05090
[22] Khosravi, B., Graphs and ranks of monoids, Comm. Algebra, 46, 7, 3006-3013 (2018) · Zbl 1390.05091
[23] Khosravi, B.; Khosravi, B., On combinatorial properties of bands, Comm. Algebra, 42, 3, 1379-1395 (2014) · Zbl 1286.05069
[24] Khosravi, B.; Khosravi, B., On Cayley graphs of semilattices of semigroups, Semigroup Forum, 86, 1, 114-132 (2013) · Zbl 1268.20064
[25] Khosravi, B.; Khosravi, B.; Khosravi, B., On color-automorphism vertex transitivity of semigroups, European J. Combin., 40, 55-64 (2014) · Zbl 1297.05110
[26] Khosravi, B.; Khosravi, B.; Khosravi, B., On the Cayley D-saturated property of semigroups, Semigroup Forum, 91, 2, 502-516 (2015) · Zbl 1339.20050
[27] Khosravi, B.; Khosravi, B.; Khosravi, B., On vertex-transitive Cayley graphs of semigroups and groups, Houston J. Math., 45, 1, 55-69 (2019) · Zbl 1479.05144
[28] Khosravi, B.; Mahmoudi, M., On Cayley graphs of rectangular groups, Discrete Math., 310, 4, 804-811 (2010) · Zbl 1208.05048
[29] Kilp, M.; Knauer, U.; Mikhalev, A., Monoids (2000), Berlin: Acts and Categories. Walter de Gruyter, Berlin · Zbl 0945.20036
[30] Knauer, U., Algebraic Graph Theory: Morphisms, Monoids and Matrices (2011), Berlin: De Gruyter, Berlin · Zbl 1338.05001
[31] Kumar, J.; Krishna, KV, The large rank of a finite semigroup using prime subsets, Semigroup Forum, 89, 2, 403-408 (2014) · Zbl 1307.20047
[32] Li, CH; Sim, HS, The graphical regular representations of finite metacyclic \(p\)-groups, European J. Combin., 21, 917-925 (2000) · Zbl 0960.05040
[33] Panma, S.; Chiangmai, NN; Knauer, U.; Arworn, S., Characterizations of Clifford semigroup digraphs, Discrete Math., 306, 12, 1247-1252 (2006) · Zbl 1096.05045
[34] Panma, S.; Knauer, U., On transitive Cayley graphs of strong semilattices of right (left) groups, Discrete Math., 309, 17, 5393-5403 (2009) · Zbl 1198.05095
[35] Praeger, C. E.: Finite Transitive Permutation Groups and Finite Vertex-transitive Graphs, Graph Symmetry: Algebraic Methods and Apllications, 497 of NATO Ser. C, Kluwer Acad. Publ., 277-318 (1997)
[36] Praeger, CE, Finite normal edge-transitive Cayley graphs, Bull. Aust. Math. Soc., 60, 207-220 (1999) · Zbl 0939.05047
[37] Wang, S., When is the cayley graph of a semigroup isomorphic to the cayley graph of a group, Math. Slovaca, 67, 1, 33-40 (2017) · Zbl 1399.05107
[38] Wang, S.; Zhang, D., A classification of vertex-transitive Cayley digraphs of strong semilattices of completely simple semigroups, Math. Slovaca, 62, 5, 829-840 (2012) · Zbl 1313.05174
[39] Xu, MY, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math., 182, 309-319 (1998) · Zbl 0887.05025
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.