Geodesic
Framed $4$-graphs: Euler tours, Gauss circuits and rotating circuits
Sbornik. Mathematics, Tome 202 (2011) no. 9, pp. 1303-1326 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider connected finite $4$-valent graphs with the structure of opposite edges at each vertex (framed $4$-graphs). For any of such graphs there exist Euler tours, in travelling along which at each vertex we turn from an edge to a nonopposite one (rotating circuits); and at the same time, it is not true that for any such graph there exists an Euler tour passing from an edge to the opposite one at each vertex (a Gauss circuit). The main result of the work is an explicit formula connecting the adjacency matrices of the Gauss circuit and an arbitrary Euler tour. This formula immediately gives us a criterion for the existence of a Gauss circuit on a given framed $4$-graph. It turns out that the results are also valid for all symmetric matrices (not just for matrices realisable by a chord diagram). Bibliography: 24 titles.
Keywords: framed $4$-graphs, rotating circuit, adjacency matrix.
Mots-clés : Euler tour, Gauss circuit 
@article{SM_2011_202_9_a2,
     author = {D. P. Il'yutko},
     title = {Framed $4$-graphs: {Euler} tours, {Gauss} circuits and rotating circuits},
     journal = {Sbornik. Mathematics},
     pages = {1303--1326},
     year = {2011},
     volume = {202},
     number = {9},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2011_202_9_a2/}
}
TY  - JOUR
AU  - D. P. Il'yutko
TI  - Framed $4$-graphs: Euler tours, Gauss circuits and rotating circuits
JO  - Sbornik. Mathematics
PY  - 2011
SP  - 1303
EP  - 1326
VL  - 202
IS  - 9
UR  - http://geodesic.mathdoc.fr/item/SM_2011_202_9_a2/
LA  - en
ID  - SM_2011_202_9_a2
ER  - 
%0 Journal Article
%A D. P. Il'yutko
%T Framed $4$-graphs: Euler tours, Gauss circuits and rotating circuits
%J Sbornik. Mathematics
%D 2011
%P 1303-1326
%V 202
%N 9
%U http://geodesic.mathdoc.fr/item/SM_2011_202_9_a2/
%G en
%F SM_2011_202_9_a2
D. P. Il'yutko. Framed $4$-graphs: Euler tours, Gauss circuits and rotating circuits. Sbornik. Mathematics, Tome 202 (2011) no. 9, pp. 1303-1326. http://geodesic.mathdoc.fr/item/SM_2011_202_9_a2/

[1] D. P. Ilyutko, V. O. Manturov, “Introduction to graph-link theory”, J. Knot Theory Ramifications, 18:6 (2009), 791–823 | DOI | MR | Zbl

[2] D. P. Ilyutko, V. O. Manturov, “Graph-links”, Dokl. Math., 80:2 (2009), 739–742 | DOI | MR | Zbl

[3] V. O. Manturov, “Embeddings of 4-valent framed graphs into 2-surfaces”, Dokl. Math., 79:1 (2009), 56–58 | DOI | MR

[4] D. Bar-Natan, “On the Vassiliev knot invariants”, Topology, 34:2 (1995), 423–472 | DOI | MR | Zbl

[5] S. V. Chmutov, S. V. Duzhin, S. K. Lando, “Vassiliev knot invariants. I. Introduction”, Singularities and bifurcations, Adv. Soviet Math., 21, Amer. Math. Soc., Providence, RI, 1994, 117–126 ; “II. Intersection graph conjecture for trees”, 127–134 ; “III. Forest algebra and weighted graphs”, 135–145 | MR | Zbl | MR | Zbl | MR | Zbl

[6] M. Goussarov, M. Polyak, O. Viro, “Finite-type invariants of classical and virtual knots”, Topology, 39:5 (2000), 1045–1068 | DOI | MR | Zbl

[7] G. Cairns, D. M. Elton, “The planarity problem for signed Gauss words”, J. Knot Theory Ramifications, 2:4 (1993), 359–367 | DOI | MR | Zbl

[8] G. Cairns, D. M. Elton, “The planarity problem. II”, J. Knot Theory Ramifications, 5:2 (1996), 137–144 | DOI | MR | Zbl

[9] R. C. Read, P. Rosenstiehl, “On the Gauss crossing problem”, Combinatorics (Keszthely, Hungary, 1976), Colloq. Math. Soc. Janos Bolyai, 18, North-Holland, Amsterdam–New-York, 1978 | MR | Zbl

[10] V. O. Manturov, “A proof of Vassiliev's conjecture on the planarity of singular links”, Izv. Math., 69:5 (2005), 1025–1033 | DOI | MR | Zbl

[11] V. Manturov, Knot theory, Chapman Hall, Boca Raton, FL, 2004 | MR | Zbl

[12] A. Kotzig, “Eulerian lines in finite 4-valent graphs and their transformations”, Theory of graphs (Tihany, Hungary, 1966), Academic Press, New York, 1968, 219–230 | MR | Zbl

[13] V. G. Turaev, “Cobordisms of words”, Commun. Contemp. Math., 10, suppl. 1 (2008), 927–972 ; arXiv: math.CO/0511513v2 | DOI | MR | Zbl

[14] D. Bar-Natan, S. Garoufalidis, “On the Melvin–Morton–Rozansky conjecture”, Invent. Math., 125:1 (1996), 103–133 | DOI | MR | Zbl

[15] M. Cohn, A. Lempel, “Cycle decomposition by disjoint transpositions”, J. Combinatorial Theory Ser. A, 13:1 (1972), 83–89 | DOI | MR | Zbl

[16] G. Moran, “Chords in a circle and linear algebra over $GF(2)$”, J. Combin. Theory Ser. A, 37:3 (1984), 239–247 | DOI | MR | Zbl

[17] E. Soboleva, “Vassiliev knot invariants coming from Lie algebras and 4-invariants”, J. Knot Theory Ramifications, 10:1 (2001), 161–169 | DOI | MR | Zbl

[18] L. Traldi, Binary nullity, Euler circuits and interlace polynomials, arXiv: 0903.4405

[19] J. Jonsson, “On the number of Euler trails in directed graphs”, Math. Scand., 90:2 (2002), 191–214 | MR | Zbl

[20] V. O. Manturov, “The bracket semigroup of knots”, Math. Notes, 67:4 (2000), 468–478 | DOI | MR | Zbl

[21] A. T. Fomenko, “The theory of invariants of multidimensional integrable Hamiltonian systems (with arbitrary many degrees of freedom). Molecular table of all integrable systems with two degrees of freedom”, Topological classification of integrable systems, Adv. Soviet Math., 6, Amer. Math. Soc., Providence, RI, 1991, 1–35 | MR | Zbl

[22] A. Bouchet, “Circle graph obstructions”, J. Combin. Theory Ser. B, 60:1 (1994), 107–144 | DOI | MR | Zbl

[23] D. P. Ilyutko, An equivalence between the set of graph-knots and the set of homotopy classes of looped graphs, arXiv: 1001.0360

[24] L. Traldi, L. Zulli, A bracket polynomial for graphs, arXiv: 0808.3392