Semigroups with outerplanar Cayley graphs

D. V. Solomatin

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 8 (2011), pp. 191-212.

Résumé

We describe some semigroups with outerplanar Cayley graphs.

Détail

Keywords: planar, outerplanar, Cayley graph, semigroups.

Bibliographie

[1] Zh.T. Belenkova, Vse ploskie grafy Keli gruppy $S_4$, Preprint, Omskii gosuniversitet, Omsk, 1997

[2] Zh.T. Belenkova, V.A. Romankov, Ploskie grafy Keli konechnykh grupp, Preprint, Omskii gosuniversitet, Omsk, 1997

[3] Zh.T. Belenkova, V.A. Romankov, “Regulyarnye grafy Keli”, Sib. mat. zhurn., Deponirovana v VINITI, 802-B97, 1997

[4] V.A. Evstigneev, Primenenie teorii grafov v programmirovanii, ed. A. P. Ershov, Nauka. Glavnaya redaktsiya fiziko-matematicheskoi literatury, Moskva, 1985 | MR

[5] V.A. Emelichev, O.I. Melnikov, V.I. Saravanov, R.I. Tyshkevich, Lektsii po teorii grafov, Nauka, Moskva, 1990 | MR | Zbl

[6] A.A. Zykov, Osnovy teorii grafov, Nauka. Gl.red.fiz.-mat.lit., Moskva, 1987 | MR | Zbl

[7] R. Lindon, P. Shupp, Kombinatornaya teoriya grupp, Mir, Moskva, 1980 | MR

[8] V. Lipskii, Kombinatorika dlya programmistov, Per. s polsk., Mir, Moskva, 1988

[9] L.Yu. Polyakova, “Rezolventy dlya svobodnykh chastichno kommutativnykh monoidov”, Sibirskii matematicheskii zhurnal, 48:6 (2007), 1295–1304 | MR | Zbl

[10] A. Skopenkov, Minikurs po topologicheskoi teorii grafov http://dfgm.math.msu.su/files/skopenkov/kuratow.pdf

[11] D.V. Solomatin, “Konechnye svobodnye kommutativnye polugruppy s planarnymi grafami Keli”, Mezhvuzovskii sbornik nauchnykh trudov: Ezhegodnik, Matematika i informatika: nauka i obrazovanie, 3, Izd-vo OmGPU, Omsk, 2003, 32–38

[12] D.V. Solomatin, “O dopustimosti nekotorykh grafov v kachestve grafov Keli polugrupp”, Mezhvuzovskii sbornik nauchnykh trudov: Ezhegodnik, Matematika i informatika: nauka i obrazovanie, 4, Izd-vo OmGPU, Omsk, 2004, 32–34

[13] D.V. Solomatin, “Rassypchatye polugruppy s planarnymi grafami Keli”, Mezhdunarodnaya algebraicheskaya konferentsiya v Ekaterinburge, posvyaschennaya stoletiyu so dnya rozhdeniya P.G.Kontorovicha i 70-letiyu L.N.Shevrina (tezisy dokladov), Izd-vo UrGU, Ekaterinburg, 2005, 14–15

[14] D.V. Solomatin, “Konechnye svobodnye kommutativnye monoidy, dopuskayuschie planarnyi graf Keli”, Vestnik Omskogo universiteta, 4, Izd-vo OmGU, Omsk, 2005, 36–38

[15] D.V. Solomatin, “Rassypchatye polugruppy s planarnymi grafami Keli”, Izvestiya VGPU: Seriya «Estestvennye i matematicheskie nauki», 13, Izd-vo «Peremena», Volgograd, 2005, 27–31

[16] D.V. Solomatin, “Pryamye proizvedeniya tsiklicheskikh monoidov i polu-grupp s nulem, dopuskayuschie planarnyi graf Keli”, Mezhvuzovskii sbornik nauchnykh trudov: Ezhegodnik, Matematika i informatika: nauka i obrazovanie, 6, Izd-vo OmGPU, Omsk, 2006, 51–63

[17] D.V. Solomatin, “Pryamye proizvedeniya tsiklicheskikh polugrupp, dopuskayuschie planarnyi graf Keli”, Sibirskie Elektronnye Matematicheskie Izvestiya, 3 (2006), 238–252 http://semr.math.nsc.ru | MR | Zbl

[18] D.V. Solomatin, Opredelenie planarnosti grafov Keli pryamykh proizvedenii tsiklicheskikh polugrupp, Programma dlya EVM, zaregistrirovannaya v OFAP 50200501609 ot 24 noyabrya 2005 goda

[19] D.V. Solomatin, Proverka dopustimosti grafa v kachestve grafa Keli polugruppy, Programma dlya EVM, zaregistrirovannaya v OFAP 50200600078 ot 02 fevralya 2006 goda

[20] D.V. Solomatin, “Konechnoporozhdennye polugruppy s odnim opredelyayuschim sootnosheniem i s tozhdestvom, dopuskayuschie planarnye grafy Keli”, Mezhvuzovskii sbornik nauchnykh trudov: Ezhegodnik, Matematika i informatika: nauka i obrazovanie, 6, Izd-vo OmGPU, Omsk, 2007, 42–48

[21] D.V. Solomatin, “Ordinalnye summy pryamougolnykh polugrupp, dopuskayuschie planarnye grafy Keli”, Mezhvuzovskii sbornik nauchnykh trudov: Ezhegodnik, Matematika i informatika: nauka i obrazovanie, 7, Izd-vo OmGPU, Omsk, 2008, 33–41

[22] D.V. Solomatin, “Svobodnye chastichno kommutativnye polugruppy i $n$-veernye polureshetki s planarnymi grafami Keli”, Mezhvuzovskii sbornik nauchnykh trudov: Ezhegodnik, Matematika i informatika: nauka i obrazovanie, 8, Izd-vo OmGPU, Omsk, 2009, 36–39

[23] D.V. Solomatin, “Svobodnye chastichno kommutativnye nilpotentnye polugruppy s planarnymi grafami Keli”, Mezhdunarodnaya konferentsiya «Maltsevskie chteniya», posvyaschennaya stoletiyu so dnya rozhdeniya A.I.Maltseva (tezisy dokladov), Izd-vo NGU, Novosibirsk, 2009, 166–167

[24] D.V. Solomatin, “O kriteriyakh planarnosti dlya grafov Keli polugrupp”, Mezhvuzovskii sbornik nauchnykh trudov: Ezhegodnik, Matematika i informatika: nauka i obrazovanie, 9, Izd-vo OmGPU, Omsk, 2010, 44–46

[25] D.V. Solomatin, “Veroyatnostnyi algoritm obnaruzheniya podgrafa, gomeomorfnogo zadannomu”, Stokhasticheskie modeli v biologii i predelnye algebry (Stochastic models in biology and limit algebras), Mezhdunarodnaya konferentsiya (2–7 avgusta, 2010 g.), Trudy konferentsii / Om. filial In-ta matematiki im. S.L.Soboleva SO RAN, Izd-vo Om. gos. un-ta, Omsk, 2010, 98–100

[26] Kh. Tsishang, E. Fogt, Kh.-D. Koldevai, Poverkhnosti i razryvnye gruppy, Nauka, Moskva, 1988 | MR

[27] L.N. Shevrin, M.V. Volkov, “Tozhdestva polugrupp”, Izvestiya vysshikh uchebnykh zavedenii: Matematika, 1985, no. 11, 3–47 | MR | Zbl

[28] L.N. Shevrin, “Polugruppy”, Obschaya algebra, Gl. IV, v. 2, ed. L.A. Skornyakov, Nauka, Moskva, 1991, 11–191

[29] V. Diekert, Y. Métivier, “Partial commutation and traces”, Handbook of formal languages, v. 3, Springer-Verl., Berlin, 1997, 457–533 | MR

[30] L. Babai, “Some applications of graph contractions”, J. Graph Theory, 1 (1977), 125–130 | DOI | MR | Zbl

[31] N. Biggs, Algebraic Graph Theory, Cambridge University Press, 1993 | MR | Zbl

[32] G. Cooperman, L. Finkelstein, N. Sarawagi, “Application of Cayley graphs”, Appl. Algebra, Alg. Algo. End Error-Correcting Codes, Lecture Notes in Comp. Sci., Springer-Verlag, 508–520 | MR

[33] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969 | MR | Zbl

[34] M.-C. Heydemann, “Cayley graphs and interconnection networks”, Graph Symmetry: Algebraic Methods and Applications, eds. G.Hahn and G.Sabidussi, Kluwer, Dordrecht, 1997, 167–224 | MR | Zbl

[35] A.V. Kelarev, “On undirected Cayley graphs”, Australasian Journal Combinatorics, 25 (2002), 73–78 | MR | Zbl

[36] A.V. Kelarev, C.E. Praeger, “On transitive Cayley graphs of groups and semigroups”, European Journal of Combinatorics, 24 (2003), 59–72 | DOI | MR | Zbl

[37] A.V. Kelarev, S.J. Quinn, “A Combinatorial Property and Cayley Graphs of Semigroups”, Semigroup Forum, 66 (2003), 89–96 | DOI | MR | Zbl

[38] A.V. Kelarev, J.C. Meakin, “On complete and bipartite Cayley graphs”, Arbeitstagung Allgemeine Algebra, v. 62, Abstracts, June 14–17, 2001, Linz, Austria, 2001, 25 (Conference Extract)

[39] S.W. Margolis, J.C. Meakin, “$E$-unitary inverse monoids and the Cayley graph of a group representation”, Journal of Pure and Applied Algebra, 58 (1989), 45–76 | DOI | MR | Zbl

[40] H. Maschke, “The representation of finite groups”, Amer. J. Math., 18 (1896), 156–194 | DOI | MR | Zbl

[41] A. Oliveira, P. Silva, “Inverse automata and monoids and the undecidability of the Cayley subgraph problem for groups”, Glasg. Math. J., 42 (2000), 421–437 | DOI | MR | Zbl

[42] B. Steinberg, “Finite state automata: a geometric approach”, Trans. Amer. Math. Soc., 353 (2001), 3409–3464 | DOI | MR | Zbl

[43] B. Zelinka, “Graphs of Semigroups”, Casopis. Pest. Mat., 106 (1981), 407–408 | MR | Zbl