Найдены две бесконечные серии полугрупп, свойство внешнепланарности графов Кэли в которвіх эквивалентно свойству обобщённой внешнепланарности их графов Кэли, но не эквивалентно свойству планарности, и одна бесконечная серия полугрупп, свойство обобщённой внешнепланарности графов Кэли которых эквивалентно свойству планарности их графов Кэли, но не эквивалентно внешнепланарности. Доказано, что граф Кэли конечной полугруппы не изоморфен ни одному из запрещённых подграфов Седлачека, взятых с любой ориентацией и раскраской рёбер, по характеристическому свойству обобщённой внешнепланарности.
Скачать электронную версию публикации
Загружен, раз: 7
- Title Сопоставление свойств внешнепланарности и обобщённой внешнепланарности графов Кэли планарных полугрупп
- Headline Сопоставление свойств внешнепланарности и обобщённой внешнепланарности графов Кэли планарных полугрупп
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 64
- Date:
- DOI 10.17223/20710410/64/2
Ключевые слова
графы Чартрэнда-Харари, графы Седлачека, полугруппы с планарным и графами КэлиАвторы
Ссылки
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.
Сопоставление свойств внешнепланарности и обобщённой внешнепланарности графов Кэли планарных полугрупп | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/2
Скачать полнотекстовую версию
Загружен, раз: 142