Прямые произведения циклических полугрупп, допускающие вершинно-внешнепланарные графы Кэли
DOI:
https://doi.org/10.52575/2687-0959-2026-58-1-44-53Ключевые слова:
циклические полугруппы, прямые произведения полугрупп, графы Кэли, вершинно-внешнепланарные графы, теория графов, теория полугруппАннотация
В настоящей работе исследованы прямые произведения циклических полугрупп, для которых графы Кэли обладают свойством вершинной внешнепланарности. Сформулированы и доказаны критерии, задающие необходимые и достаточные условия существования вершинно-внешнепланарных графов Кэли в указанном классе, а также проведена классификация полугрупп, удовлетворяющих этим условиям, по количеству множителей. Основной результат включает установление точных условий внешнепланарности на уровне параметров индекса, порядка и количества элементов системы образующих, входящих в произведение циклических полугрупп; выделение и описание семейств прямых произведений, для которых вершинная внешнепланарность достигается и сохраняется при естественных операциях; демонстрацию соответствия между алгебраическими ограничениями структуры произведения и топологическими свойствами графов Кэли. Как следствие получен исчерпывающий перечень полугрупп, являющихся прямым произведением неодноэлементных циклических полугрупп, которые допускают планарный граф Кэли, но при этом не допускают вершинно-внешнепланарный граф Кэли.
Скачивания
Библиографические ссылки
Список литературы
Dziobiak S. Excluded-minor characterization of apex-outerplanar graphs. LSU Doctoral Dissertations. 3102; 2011. 83 p. https://repository.lsu.edu/gradschool_dissertations/3102
Ding G., Dziobiak S, Excluded-minor characterization of apex-outerplanar graphs. Graphs and Combinatorics. 2016;32(2):583–627.
Chatzidimitriou D. et al., Sparse obstructions for minor-covering parameters. Discrete Appl. Math. 2020;278:28–50.
Donkers H. et al., Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size. Algorithmica. 2022;84(11):3407–3458.
Eppstein D. On the biplanarity of blowups. J. Graph Algorithms Appl. 2024;28(2):83–99.
JobsonA.S., K´ezdyA.E.Allminor-minimal apex obstructionswith connectivity two. Electron. J. Comb. 2021;28(1):Research Paper P1.23, 58 p.
Leivaditis A. et al., Minor-obstructions for apex sub-unicyclic graphs. Acta Math. Univ. Comen. New Ser. 2019;88(3):903–910.
Leivaditis A. et al., Minor-obstructions for apex sub-unicyclic graphs. Discrete Appl. Math. 2020;284:538–555.
Leivaditis A. et al., Minor obstructions for apex-pseudoforests. Discrete Math. 2021;344(10): Article ID 112529, 31 p.
Mattman T.W. Forbidden minors: finding the finite few. in: A primer for undergraduate research. From groups and tiles to frames and vaccines. Cham: Birkh¨auser. 2017;85–97
Sau I. et al., k-apices of minor-closed graph classes. I: Bounding the obstructions. J. Comb. Theory, Ser. B 2023;161:180–227.
Savitsky T.J., Schluchter S.A. Some excluded minors for the spindle surface. J. Comb. Math. Comb. Comput. 2024;119:217–232.
Соломатин Д.В. Прямые произведения циклических полугрупп, допускающие внешнепланарные графы Кэли и их обобщения. Прикладная математика & Физика. 2024;56(1):13–20.
Harary F. Graph Theory: Advanced Book Program Series. Boulder: Westview Press; 1994. 284 p.
Zelinka B. Graphs of Semigroups. Casopis. Pest. Mat. 1981;106:407–408.
Соломатин Д.В. Исследования полугрупп с планарными графами Кэли: результаты и проблемы. Прикладная Дискретная Математика. 2021;54:5–57.
References
Dziobiak S, Excluded-minor characterization of apex-outerplanar graphs. LSU Doctoral Dissertations. 3102; 2011. 83 p. https://repository.lsu.edu/gradschool_dissertations/3102
Ding G., Dziobiak S, Excluded-minor characterization of apex-outerplanar graphs. Graphs and Combinatorics. 2016;32(2):583–627.
Chatzidimitriou D. et al., Sparse obstructions for minor-covering parameters. Discrete Appl. Math. 2020;278:28–50.
Donkers H. et al., Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size. Algorithmica. 2022;84(11):3407–3458.
Eppstein D. On the biplanarity of blowups. J. Graph Algorithms Appl. 2024;28(2):83–99.
Jobson AS., K´ezdy AE, Allminor-minimal apex obstructions with connectivity two. Electron. J. Comb. 2021;28(1):Research Paper P1.23, 58 p.
Leivaditis A. et al., Minor-obstructions for apex sub-unicyclic graphs. Acta Math. Univ. Comen. New Ser. 2019;88(3):903–910.
Leivaditis A. et al., Minor-obstructions for apex sub-unicyclic graphs. Discrete Appl. Math. 2020;284:538–555.
Leivaditis A. et al., Minor obstructions for apex-pseudoforests. Discrete Math. 2021;344(10): Article ID 112529, 31 p.
Mattman TW, Forbidden minors: finding the finite few. in: A primer for undergraduate research. From groups and tiles to frames and vaccines. Cham: Birkh¨auser. 2017;85–97
Sau I. et al., k-apices of minor-closed graph classes. I: Bounding the obstructions. J. Comb. Theory, Ser. B 2023;161:180–227.
Savitsky TJ., Schluchter SA, Some excluded minors for the spindle surface. J. Comb. Math. Comb. Comput. 2024;119:217–232.
Solomatin DV, Direct Products of Cyclic Semigroups Allowing Outerplanar Cayley Graphs and Their Generalizations. Applied Mathematics & Physics. 2024;56(1):13–20. (in Russ.)
Harary F. Graph Theory: Advanced Book Program Series. Boulder: Westview Press; 1994. 284 p.
Zelinka B. Graphs of Semigroups. Casopis. Pest. Mat. 1981;106:407–408.
Solomatin DV, Researches of semigroups with planar Cayley graphs: results and problems. Prikladnaya Diskretnaya Matematika. 2021;54:5–57. (in Russ.)
Просмотров аннотации: 0
Поделиться
Опубликован
Как цитировать
Выпуск
Раздел
Copyright (c) 2026 Прикладная математика & Физика
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
