Прямые произведения циклических полугрупп, допускающие внешнепланарные графы Кэли и их обобщения
DOI:
https://doi.org/10.52575/2687-0959-2024-56-1-13-20Ключевые слова:
полугруппа, граф Кэли полугруппы, внешнепланарный граф, прямое произведениеАннотация
Доказаны характеристические свойства внешнепланарности и обобщенной внешнепланарности графов Кэли прямых произведений циклических полугрупп в терминах копредставлений. Основная идея доказательства теорем, приведенных в статье, заключается в следующем: если обнаруженные в результате исследования условия выполнены, то полугруппа допускает обобщенную внешнеплоскую [соответственно, внешнеплоскую] укладку её графа Кэли (то есть такую укладку, при которой каждое ребро принадлежит одной грани хотя бы одной из своих вершин, и ребра не пересекаются в плоскости) [соответственно, такую укладку, при которой все вершины принадлежат одной грани, а ребра не пересекаются в плоскости]; обратно, по закону контрапозиции, если найденные условия не выполнены, то указывается подграф, гомеоморфный одной из запрещенных конфигураций. Рассуждения ведутся по аналогии с исследованиями полугрупп, допускающих планарные графы, при этом запрещенные конфигурации меняются на новые, в силу критерия Чартрэнда–Харари и Седлачека.
Скачивания
Библиографические ссылки
Мартынов П.О., Соломатин Д.В. Конечные свободные коммутативные полугруппы и полугруппы с нулём, допускающие обобщенные внешнепланарные графы Кэли. Вестник Омского университета. 2014;3(73):22–26.
Мартынов П.О. Конечные свободные коммутативные моноиды, допускающие обобщенно внешнепланарные графы Кэли. Вестник Омского университета. 2015;4:6–9.
Мартынов П.О. Рассыпчатые полугруппы, допускающие обобщенные внешнепланарные графы Кэли. Вестник Омского университета. 2018;3:6–9.
Harary F. Graph Theory: Advanced Book Program Series. Boulder: Westview Press; 1994. 284 p.
Zelinka B. Graphs of Semigroups. Cˇasopis pro peˇstova’ni’matematiky. 1981;106:407–408. (in Czech)
Maschke H. The representation of finite groups. American Journal of Mathematics. 1896;18:156–194.
Емеличев В.А., Мельников О.И., Сараванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука; 1990. 384 с.
Зыков А.А. Основы теории графов. М.: Наука; 1987. 384 с.
Sedla’cˇek J. On a generalization of outerplanar graphs. Cˇasopis pro peˇstova’ni’matematiky. 1988;113(2):213–218. (in Czech)
Sedla’cˇek J. On local properties of graphs again. Cˇasopis pro peˇstova’ni’matematiky. 1989;114(4): 381–390. (in Czech)
Oubi ˜ na L., Zucchello R.A Generalization of outerplanar graphs. Discrete Mathematics, North-Holland. 1984;51:243–249.
Sysło M.M. On some generalizations of outerplanar graphs: Results and open problems. In: Tinhofer, G., Schmidt, G. (eds) Graph-Theoretic Concepts in Computer Science. WG 1986. Lecture Notes in Computer Science. Springer, Berlin: Heidelberg; 1987. 246 p. DOI: 10.1007/3-540-17218-1_56
C’aceres J., M’arquez A. A linear algorithm to recognize maximal generalized outerplanar graphs. Mathematica Bohemica. 1997;122(3):225–230.
Соломатин Д.В. Прямые произведения циклических полугрупп, допускающие планарный граф Кэли. Сибирские Электронные Математические Известия. 2006;3:238–252.
Соломатин Д.В. Строение полугрупп, допускающих внешнепланарные графы Кэли. Сибирские Электронные Математические Известия. 2011;8:191–212.
Просмотров аннотации: 83
Поделиться
Опубликован
Как цитировать
Выпуск
Раздел
Copyright (c) 2024 Прикладная математика & Физика
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.