Критерий цикличности обобщенного крестового графа с помощью минимальных запрещенных миноров

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

В своей работе Дж. Джилен и С. Оум нашли классы минимальных запрещенных миноров для цикличности простого графа с точностью до шарнирных преобразований и для эйлеровости дельта-матроида. Классы эквивалентности циклических простых графов по шарнирным преобразованиям и дельта-матроиды возникают при исследовании эйлеровых циклов на крестовых графах (4-графах с крестовой структурой). Полученные Джиленом и Оумом результаты полностью опираются на некоторые леммы из их совместной работы, которые, как мы покажем ниже, не совсем верны.В настоящей работе рассматриваются обобщенные крестовые графы, которые появляются при описании поворачивающих обходов на крестовых графах. Для таких графов мы ищем критерий цикличности, повторяя и дополняя рассуждения Джилена и Оума, а также подправляя неправильно сформулированные утверждения. В результате мы получаем тот же самый список, состоящий из 166 неэквивалентных графов, минимальных запрещенных миноров для цикличности обобщенного крестового графа.Библиография: 14 названий.

Об авторах

Виктор Петрович Ильютко

Московский государственный университет имени М. В. Ломоносова, факультет вычислительной математики и кибернетики

Денис Петрович Ильютко

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Email: ilyutko@yandex.ru
кандидат физико-математических наук, доцент

Список литературы

  1. N. Robertson, P. D. Seymour, “Graph minors. XX. Wagner's conjecture”, J. Combin. Theory Ser. B, 92:2 (2004), 325–357
  2. A. Bouchet, “Circle graph obstructions”, J. Combin. Theory Ser. B, 60:1 (1994), 107–144
  3. 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.
  4. 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.
  5. Д. П. Ильютко, “Оснащенные 4-графы: эйлеровы циклы, гауссовы циклы и поворачивающие обходы”, Матем. сб., 202:9 (2011), 53–76
  6. D. P. Ilyutko, V. O. Manturov, “Introduction to graph-link theory”, J. Knot Theory Ramifications, 18:6 (2009), 791–823
  7. I. Nikonov, “A new proof of Vassiliev's conjecture”, J. Knot Theory Ramifications, 23:7 (2014), 1460005, 28 pp.
  8. В. О. Мантуров, “Доказательство гипотезы В. А. Васильева о планарности сингулярных зацеплений”, Изв. РАН. Сер. матем., 69:5 (2005), 169–178
  9. 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
  10. J. Geelen, S. Oum, “Circle graph obstructions under pivoting”, J. Graph Theory, 61:1 (2009), 1–11
  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
  12. 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.
  13. Д. П. Ильютко, В. С. Сафина, “Граф-зацепления: нереализуемость, ориентация и полином Джонса”, Топология, СМФН, 51, РУДН, М., 2013, 33–63
  14. A. Bouchet, “Graphic presentations of isotropic systems”, J. Combin. Theory Ser. B, 45:1 (1988), 58–76

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Ильютко В.П., Ильютко Д.П., 2023

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).