Action graph of a semigroup act & its functorial connection

Document Type : Research Paper

Authors

1 Mathematics, Faculty of Science, Jadavpur University, Kolkata-700032 India

2 Department of Mathematics, Garhbeta College, Paschim Medinipur-721127, India

3 Mathematics, Faculty of Science, Jadavpur University, Kolkata-700032, India.

Abstract

In this paper we define C-induced action graph G(S,a,C;A) corresponding to a semigroup act (S,a,A) and a subset C of S. This generalizes many interesting graphs including Cayley Graph of groups and semigroups, Transformation Graphs (TRAG), Group Action Graphs (GAG), Derangement Action Graphs, Directed Power Graphs of Semigroups etc. We focus on the case when C = S and name the digraph, so obtained, as Action Graph of a Semigroup Act (S, a, A). Some basic structural properties of this graph follow from algebraic properties of the underlying semigroup and its action on the set. Action graph of a strongly faithful act is also studied and graph theoretic characterization of a strongly faithful semigroup act as well as that of idempotents in a semigroup are obtained. We introduce the notion of strongly transitive digraphs and based on this we characterize action graphs of semigroup acts in the class of simple digraphs. The simple fact that morphism between semigroup acts leads to digraph homomorphism between corresponding action graphs, motivates us to represent action graph construction as a functor from the category of semigroup acts to the category of certain digraphs. We capture its functorial properties, some of which signify previous results in terms of Category Theory.

Keywords

Main Subjects

References

[1] Adamek, J., Herrlich, H., and Strecker, G.E., “Abstract and Concrete Categroies: The Joy of Cats”, Wiley, 1990.
[2] Annexstein, F., Baumslag, M., and Rosenberg, A.L., Group action graphs and parallel architectures, SIAM J. Comput. 19 (1990), 544-569.
[3] Bang-Jensen, J. and Huang, J., Quasi-transitive digraphs, J. Graph Theory 20(2) (1995), 141-161.
[4] Biggs, N.L., “Algebraic Graph Theory”, Cambridge University Press, 1996.
[5] Chakrabarty, I., Ghosh, S., and Sen, M.K., Undirected power graphs of semigroups, Semigroup Forum 78 (2009), 410-426.
[6] Cormen et al., “Introduction to Algorithms”, Third Edition, The MIT Press, 2009.
[7] Dénes, J., Connections between transformation semigroups and graphs, Theory of Graphs, 93-101, Gordon and Breach, (1967).
[8] Dénes, J., Some combinatorial properties of transformations and their connections with the theory of graphs, J. Combin. Theory 9 (1969), 108-116.
[9] Delfan, A., Rasouli, H., and Tehranian, A., On the inclusion graphs of S-acts, J. Math. Computer Sci. 18 (2018), 357–363.
[10] Delfan, A., Rasouli, H., and Tehranian, A., Intersection graphs associated with semi- group acts, Categ. Gen. Algebr. Struct. Appl. 11 (2019), 131-148.
[11] East, J., Gadouleau, M., and Mitchell, J.D., Structural aspects of semigroups based on digraphs, Algebr. Comb. 2(5) (2019), 711–733.
[12] Estaji, A.A., Haghdadi, T., and Estaji, A.As., Zero divisor graphs for S-Act, Lobachevskii J. Math. 36(1) (2015), 1–8.
[13] Fan, S. and Zeng, Y., On Cayley graphs of bands, Semigroup Forum 74 (2007), 99–105.
[14] Fedorova, M., Faithful group actions and Schreier graphs, Carpathian Math. Publ. 9(2) (2017), 202–207.
[15] Godsil, G. and Royle, G., “Algebraic Graph Theory”, Springer, 2001.
[16] Howie, J.M., “Fundamentals of Semigroup Theory”, Clarendon Press, 1995.
[17] Iradmusa, M.N. and Praeger, C.E., Derangement action digraphs and graphs, Euro- pean J. Combin. 80 (2019), 361–372.
[18] Kelarev, A.V. and Praeger, C.E., On transitive Cayley graphs of groups and semi- groups, European J. Combin. 24 (2003), 59-72.
[19] Kelarev, A.V. and Quinn, S.J., Directed graphs and combinatorial properties of semi- groups, J. Algebra 251 (2002), 16-26.
[20] Khosravi, B. and Khosravi, B., A characterization of Cayley graphs of Brandt semi- groups, Bull. Malays. Math. Sci. Soc. (2) 35(2) (2012), 399-410.
[21] Kilp, M., Knauer, U., and Mikhalev, A., “Monoids, Acts and Categories”, Walter de Gruyter, 2000.
[22] Knauer, U. and Knauer, K., “Algebraic Graph Theory”, De Gruyter Studies, 2nd  Edition, 2019.
[23] Knauer, U., Wang, Y., and Zhang, X., Functorial properties of Cayley constructions, Acta Comment. Univ. Tartu. Math. 10 (2006), 17–29.
[24] Mac Lane, S., “Categories for the Working Mathematicians”, 2nd  Edition, Springer, 1997.
[25] Malnič, A., Action graphs and coverings, Discrete Math. 244 (2002), 299–322.
[26] Panma, S., Knauer, U., and Arworn, Sr., On transitive Cayley graphs of strong semilattices of right (left) groups, Discrete Math. 309 (2009), 5393–5403.
[27] West, D.B., “Introduction to Graph Theory”, Prentice Hall, 2001.
[28] Zelinka, B., Graphs of semigroups, Časopis pro p̌estovánímatematiky 106(4) (1981), 407-408.
Categories and General Algebraic Structures with Applications
Volume 18, Issue 1
February 2023
Pages 43-80

Files

Share

How to cite

Statistics