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

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

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.

About the authors

Viktor Petrovich Ilyutko

Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics

Denis Petrovich Ilyutko

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

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

References

  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

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2023 Ilyutko V.P., Ilyutko D.P.

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

 

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