A circle criterion for a generalized cross graph in terms of minimal excluded minors

Capa

Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Somente assinantes

Resumo

Geelen and Oum described classes of minimal excluded pivot-minors for a simple graph to be a circle graphand for a delta-matroid to be Eulerian. Pivot-equivalence classes of circle simple graphs and delta-matroids arise in the investigation of Eulerian cycles on cross graphs (4-valent graphs with cross structure). The results established by Geelen and Oum rely on some lemmas in their work, which are shown below to be not quite correct.We consider generalized cross graphs, which arise in the description of rotating circuits on cross graphs. For such graphs we derive a circle criterion: we reproduce and augment the arguments due to Geelen and Oum, and we improve some incorrectly formulated statements. As a result, we obtain the same list of 166 inequivalent graphs, the minimal excluded minors for a generalized cross graph to be a circle graph.Bibliography: 14 titles.

Sobre autores

Viktor Ilyutko

Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics

Denis Ilyutko

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Email: ilyutko@yandex.ru
Candidate of physico-mathematical sciences, Associate professor

Bibliografia

  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

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar

Declaração de direitos autorais © Ilyutko V.P., Ilyutko D.P., 2023

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

 

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