Partial automorphisms and injective partial endomorphisms of a finite undirected path. (English) Zbl 1467.05137
Summary: In this paper, we study partial automorphisms and, more generally, injective partial endomorphisms of a finite undirected path from Semigroup Theory perspective. Our main objective is to give formulas for the ranks of the monoids \(\text{IEnd}(P_n)\) and \(\text{PAut}(P_n)\) of all injective partial endomorphisms and of all partial automorphisms of the undirected path \(P_n\) with \(n\) vertices. We also describe Green’s relations of \(\text{PAut}(P_n)\) and \(\text{IEnd}(P_n)\) and calculate their cardinals.
MSC:
| 05C38 | Paths and cycles |
| 20M10 | General structure theory for semigroups |
| 20M20 | Semigroups of transformations, relations, partitions, etc. |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
References:
| [1] | Al-Kharousi, F.; Kehinde, R.; Umar, A., On the semigroup of partial isometries of a finite chain, Commun. Algebra, 44, 639-647 (2016) · Zbl 1339.20058 · doi:10.1080/00927872.2014.984838 |
| [2] | Araújo, J.; Bentz, W.; Mitchell, JD; Schneider, C., The rank of the semigroup of transformations stabilising a partition of a finite set, Math. Proc. Camb. Philos. Soc., 159, 339-353 (2015) · Zbl 1371.20055 · doi:10.1017/S0305004115000389 |
| [3] | Arworn, S., An algorithm for the numbers of endomorphisms on paths, Discrete Math., 309, 94-103 (2009) · Zbl 1215.05178 · doi:10.1016/j.disc.2007.12.049 |
| [4] | Arworn, S.; Knauer, U.; Leeratanavalee, S., Locally strong endomorphisms of paths, Discrete Math., 308, 2525-2532 (2008) · Zbl 1140.05035 · doi:10.1016/j.disc.2007.06.007 |
| [5] | Cicaló, S.; Fernandes, VH; Schneider, C., Partial transformation monoids preserving a uniform partition, Semigroup Forum, 90, 532-544 (2015) · Zbl 1325.20054 · doi:10.1007/s00233-014-9629-5 |
| [6] | Dimitrova, I.; Fernandes, VH; Koppitz, J.; Quinteiro, TM, Ranks of monoids of endomorphisms of a finite undirected path, Bull. Malays. Math. Sci. Soc., 43, 1623-1645 (2015) · Zbl 1434.05081 · doi:10.1007/s40840-019-00762-4 |
| [7] | Fan, S.: On end-regular bipartite graphs. In: Combinatorics and Graph Theory. Proceedings of the Spring School and International Conference on Combinatorics, pp. 117-130. World Scientific, Singapore (1993) · Zbl 0832.05056 |
| [8] | Fan, S., The regularity of the endomorphism monoid of a split graph, Acta Math. Sin., 40, 419-422 (1997) · Zbl 0907.05047 |
| [9] | Fan, S., Retractions of split graphs and End-orthodox split graphs, Discrete Math., 257, 161-164 (2002) · Zbl 1010.05036 · doi:10.1016/S0012-365X(02)00388-6 |
| [10] | Fernandes, V.H.: Presentations for some monoids of partial transformations on a finite chain: a survey. In: Semigroups. Algorithms, Automata and Languages (Coimbra, 2001), pp. 363-378. World Scientific, River Edge, NJ (2002) · Zbl 1030.20042 |
| [11] | Fernandes, VH; Honyam, P.; Quinteiro, TM; Singha, B., On semigroups of endomorphisms of a chain with restricted range, Semigroup Forum, 89, 77-104 (2014) · Zbl 1309.20051 · doi:10.1007/s00233-013-9548-x |
| [12] | Fernandes, VH; Honyam, P.; Quinteiro, TM; Singha, B., On semigroups of orientation-preserving transformations with restricted range, Commun. Algebra, 44, 253-264 (2016) · Zbl 1339.20060 · doi:10.1080/00927872.2014.975345 |
| [13] | Fernandes, VH; Koppitz, J.; Musunthia, T., The rank of the semigroup of all order-preserving transformations on a finite fence, Bull. Malays. Math. Sci. Soc., 42, 2191-2211 (2019) · Zbl 1454.20110 · doi:10.1007/s40840-017-0598-1 |
| [14] | Fernandes, VH; Quinteiro, TM, On the ranks of certain monoids of transformations that preserve a uniform partition, Commun. Algebra, 42, 615-636 (2014) · Zbl 1290.20053 · doi:10.1080/00927872.2012.720322 |
| [15] | Fernandes, VH; Sanwong, J., On the rank of semigroups of transformations on a finite set with restricted range, Algebra Colloq., 21, 497-510 (2014) · Zbl 1301.20063 · doi:10.1142/S1005386714000431 |
| [16] | Hou, H.; Gu, R., Split graphs whose completely regular endomorphisms form a monoid, Ars Comb., 127, 79-88 (2016) · Zbl 1413.05155 |
| [17] | Hou, H.; Gu, R.; Shang, Y., The join of split graphs whose regular endomorphisms form a monoid, Commun. Algebra, 42, 795-802 (2014) · Zbl 1285.05090 · doi:10.1080/00927872.2012.724746 |
| [18] | Hou, H.; Gu, R.; Shang, Y., The join of split graphs whose quasi-strong endomorphisms form a monoid, Bull. Austral. Math. Soc., 91, 1-10 (2015) · Zbl 1307.05159 · doi:10.1017/S000497271400046X |
| [19] | Hou, H.; Luo, Y.; Cheng, Z., The endomorphism monoid of \({\bar{P}}_n \), Eur. J. Comb., 29, 1173-1185 (2008) · Zbl 1151.20050 · doi:10.1016/j.ejc.2007.06.026 |
| [20] | Hou, H.; Luo, Y.; Fan, S., End-regular and end-orthodox joins of split graphs, Ars Comb., 105, 305-318 (2012) · Zbl 1274.05215 |
| [21] | Hou, H.; Song, Y.; Gu, R., The join of split graphs whose completely regular endomorphisms form a monoid, De Gruyter Open Math., 15, 833-839 (2017) · Zbl 1367.05103 · doi:10.1515/math-2017-0071 |
| [22] | Howie, JM, Fundamentals of Semigroup Theory (1995), Oxford: Clarendon Press, Oxford · Zbl 0835.20077 |
| [23] | Huisheng, P., On the rank of the semigroup \(T_\rho (X)\), Semigroup Forum, 70, 107-117 (2005) · Zbl 1100.20043 · doi:10.1007/s00233-004-0135-z |
| [24] | Knauer, U., Algebraic Graph Theory: Morphisms, Monoids, and Matrices (2011), Berlin: De Gruyter, Berlin · Zbl 1338.05001 · doi:10.1515/9783110255096 |
| [25] | Knauer, U.; Wanichsombat, A., Completely regular endomorphisms of split graphs, Ars Comb., 115, 357-366 (2014) · Zbl 1340.05190 |
| [26] | Li, W., Split graphs with completely regular endomorphism monoids, J. Math. Res. Expos., 26, 253-263 (2006) · Zbl 1107.05043 |
| [27] | Li, W.; Chen, J., Endomorphism-regularity of split graphs, Eur. J. Comb., 22, 207-216 (2001) · Zbl 0963.05118 · doi:10.1006/eujc.2000.0443 |
| [28] | Lu, D.; Wu, T., Endomorphism monoids of generalized split graphs, Ars Comb., 11, 357-373 (2013) · Zbl 1313.05282 |
| [29] | Marki, L., Problems raised at the problem session of the colloquium on semigroups in Szeged, August 1987, Semigroup Forum, 37, 367-373 (1988) · Zbl 0692.20044 · doi:10.1007/BF02573148 |
| [30] | Michels, MA; Knauer, U., The congruence classes of paths and cycles, Discrete Math., 309, 5352-5359 (2009) · Zbl 1231.05149 · doi:10.1016/j.disc.2008.11.022 |
| [31] | Pipattanajinda, N.; Knauer, U.; Gyurov, B.; Panma, S., The endomorphism monoids of \((n-3)\)-regular graphs of order \(n\), Algebra Discrete Math., 22-2, 284-300 (2016) · Zbl 1370.05094 |
| [32] | Wilkeit, E., Graphs with a regular endomorphism monoid, Arch. Math., 66, 344-352 (1996) · Zbl 0855.05090 · doi:10.1007/BF01207836 |
| [33] | Zhao, P., On the ranks of certain semigroups of orientation preserving transformations, Commun. Algebra, 39, 4195-4205 (2011) · Zbl 1248.20067 · doi:10.1080/00927872.2010.521933 |
| [34] | Zhao, P.; Fernandes, VH, The ranks of ideals in various transformation monoids, Commun. Algebra, 43, 674-692 (2015) · Zbl 1320.20061 · doi:10.1080/00927872.2013.847946 |
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.
