We have found two infinite series of semigroups whose Cayley graphs have an outerplanarity property equivalent to the generalized outerplanarity property of their Cayley graphs, but not equivalent to the planarity property, and one infinite series of semigroups whose Cayley graphs have a generalized outerplanarity property equivalent to the planarity property of their Cayley graphs, but not equivalent to outerplanarity. It is proved that the Cayley graph of a finite semigroup is not isomorphic to any of the forbidden SedlaCek’s subgraphs by the characteristic property of generalized outer planarity with any orientation and edge coloring.
Download file
Counter downloads: 7
- Title Comparison of outerplanarity and generalized outerplanarity properties for Cayley graphs of planar semigroups
- Headline Comparison of outerplanarity and generalized outerplanarity properties for Cayley graphs of planar semigroups
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 64
- Date:
- DOI 10.17223/20710410/64/2
Keywords
Chartrand-Harari graphs, Sedlacek graphs, semigroups with planar Cayley graphsAuthors
References
Chartrand G. and Harary F. Planar permutation graphs // Annales de ГI. H. P. Section B. 1967. V.3. No. 4. P. 433-438.
Sedldcek J. О jednom zobecneni vnejskove rovinnvch graft // Casopis Pest. Mat. 1988. V. 2. No. 113. P. 213-218. (in Czech).
Schietgat L., Ramon J., and Bruynooghe M. A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics // Ann. Math. Artif.Intell. 2013. V.69. P.343-376.
Соломатин Д. В. Исследования полугрупп с планарными графами Кэли: результаты и проблемы // Прикладная дискретная математика. 2021. №54. С. 5-57.
Соломатин Д. В. Прямые произведения циклических моноидов, допускающие внешнепланарные графы Кэли и их обобщения // Вестник ТвГУ. Сер. Прикладная математика. 2023. УМ. С. 43-56.
Соломатин Д. В. Конечно порожденные полугруппы с одним определяющим соотношением и с тождеством, допускающие планарные графы Кэли // Математика и информатика: Наука и образование. 2007. №6. С. 42-48.
Шнеерсон Л. М. Тождества в полугруппах с одним определяющим соотношением // Логика, алгебра и вычисл. матем. Иваново, 1972. №1-2. С. 139-156.
Соломатин Д. В. Строение полугрупп, допускающих внешнепланарные графы Кэли j j Сиб. электрон, матем. изв. 2011. Т. 8. С. 191-212.
Almeria J. С. and Sevilla А. М. A linear algorithm to recognize maximal generalized outerplanar graphs // Mathematica Bohemica. 1997. V. 122. No.3. P.225-230.
Соломатин Д. В. Свободные частично коммутативные полугруппы и n-веерные полурешетки с планарными графами Кэли // Математика и информатика: Наука и образование. 2009. №8. С. 36-39.
Соломатин Д. В. О допустимости некоторых графов в качестве графов Кэли полугрупп // Математика и информатика: Наука и образование. 2004. №4. С. 32-34.
Comparison of outerplanarity and generalized outerplanarity properties for Cayley graphs of planar semigroups | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 64. DOI: 10.17223/20710410/64/2
Download full-text version
Counter downloads: 143