Прямые произведения циклических полугрупп, допускающие внешнепланарные графы Кэли и их обобщения

Денис Владимирович Соломатин

doi:10.52575/2687-0959-2024-56-1-13-20

Авторы

Денис Владимирович Соломатин ФГБОУ ВО "Омский государственный педагогический университет" https://orcid.org/0000-0002-9356-9890

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.