Отправить статью по E-mail Критерий цикличности обобщенного крестового графа с помощью минимальных запрещенных миноров
- Авторы: Ильютко В.П.1, Ильютко Д.П.2
-
Учреждения:
- Московский государственный университет имени М. В. Ломоносова, факультет вычислительной математики и кибернетики
- Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
- Выпуск: Том 213, № 12 (2022)
- Страницы: 53-67
- Раздел: Статьи
- URL: https://journal-vniispk.ru/0368-8666/article/view/133484
- DOI: https://doi.org/10.4213/sm9670
- ID: 133484
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
В своей работе Дж. Джилен и С. Оум нашли классы минимальных запрещенных миноров для цикличности простого графа с точностью до шарнирных преобразований и для эйлеровости дельта-матроида. Классы эквивалентности циклических простых графов по шарнирным преобразованиям и дельта-матроиды возникают при исследовании эйлеровых циклов на крестовых графах (4-графах с крестовой структурой). Полученные Джиленом и Оумом результаты полностью опираются на некоторые леммы из их совместной работы, которые, как мы покажем ниже, не совсем верны.В настоящей работе рассматриваются обобщенные крестовые графы, которые появляются при описании поворачивающих обходов на крестовых графах. Для таких графов мы ищем критерий цикличности, повторяя и дополняя рассуждения Джилена и Оума, а также подправляя неправильно сформулированные утверждения. В результате мы получаем тот же самый список, состоящий из 166 неэквивалентных графов, минимальных запрещенных миноров для цикличности обобщенного крестового графа.Библиография: 14 названий.
Ключевые слова
Об авторах
Виктор Петрович Ильютко
Московский государственный университет имени М. В. Ломоносова, факультет вычислительной математики и кибернетики
Денис Петрович Ильютко
Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
Email: ilyutko@yandex.ru
кандидат физико-математических наук, доцент
Список литературы
- N. Robertson, P. D. Seymour, “Graph minors. XX. Wagner's conjecture”, J. Combin. Theory Ser. B, 92:2 (2004), 325–357
- A. Bouchet, “Circle graph obstructions”, J. Combin. Theory Ser. B, 60:1 (1994), 107–144
- V. O. Manturov, “Framed 4-valent graph minor theory. I. Introduction. A planarity criterion and linkless embeddability”, J. Knot Theory Ramifications, 23:7 (2014), 1460002, 8 pp.
- V. O. Manturov, “Framed 4-valent graph minor theory. II. Special minors and new examples”, J. Knot Theory Ramifications, 24:13 (2015), 1541004, 12 pp.
- Д. П. Ильютко, “Оснащенные 4-графы: эйлеровы циклы, гауссовы циклы и поворачивающие обходы”, Матем. сб., 202:9 (2011), 53–76
- D. P. Ilyutko, V. O. Manturov, “Introduction to graph-link theory”, J. Knot Theory Ramifications, 18:6 (2009), 791–823
- I. Nikonov, “A new proof of Vassiliev's conjecture”, J. Knot Theory Ramifications, 23:7 (2014), 1460005, 28 pp.
- В. О. Мантуров, “Доказательство гипотезы В. А. Васильева о планарности сингулярных зацеплений”, Изв. РАН. Сер. матем., 69:5 (2005), 169–178
- R. C. Read, P. Rosenstiehl, “On the Gauss crossing problem”, Combinatorics (Keszthely, 1976), v. II, Colloq. Math. Soc. Janos Bolyai, 18, North-Holland, Amsterdam–New York, 1978, 843–876
- J. Geelen, S. Oum, “Circle graph obstructions under pivoting”, J. Graph Theory, 61:1 (2009), 1–11
- A. Kotzig, “Eulerian lines in finite $4$-valent graphs and their transformations”, Theory of graphs (Tihany, 1966), Academic Press, New York, 1968, 219–230
- V. O. Manturov, D. P. Ilyutko, Virtual knots. The state of the art, Ser. Knots Everything, 51, World Sci. Publ., Hackensack, NJ, 2013, xxvi+521 pp.
- Д. П. Ильютко, В. С. Сафина, “Граф-зацепления: нереализуемость, ориентация и полином Джонса”, Топология, СМФН, 51, РУДН, М., 2013, 33–63
- A. Bouchet, “Graphic presentations of isotropic systems”, J. Combin. Theory Ser. B, 45:1 (1988), 58–76
Дополнительные файлы
