Geodesic
Switches in Eulerian graphs
Ahad N. Zehmakan1 ; Jerri Nummenpalo1 ; Alexander Pilz1 ; Daniel Wolleb-Graf1 ; Ahad N. Zehmakan ; Jerri Nummenpalo ; Alexander Pilz ; Daniel Wolleb-Graf
1Department of Computer Science, ETH Zürich, Zürich, Switzerland
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 1087-1092 
Ahad N. Zehmakan; Jerri Nummenpalo; Alexander Pilz; Daniel Wolleb-Graf; Ahad N. Zehmakan; Jerri Nummenpalo; Alexander Pilz; Daniel Wolleb-Graf. Switches in Eulerian graphs. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 1087-1092. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a112/
@article{AMUC_2019_88_3_a112,
     author = {Ahad N. Zehmakan and Jerri Nummenpalo and Alexander Pilz and Daniel Wolleb-Graf and Ahad N. Zehmakan and Jerri Nummenpalo and Alexander Pilz and Daniel Wolleb-Graf},
     title = { Switches in {Eulerian} graphs},
     journal = {Acta mathematica Universitatis Comenianae},
     pages = {1087--1092},
     year = {2019},
     volume = {88},
     number = {3},
     url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a112/}
}
TY  - JOUR
AU  - Ahad N. Zehmakan
AU  - Jerri Nummenpalo
AU  - Alexander Pilz
AU  - Daniel Wolleb-Graf
AU  - Ahad N. Zehmakan
AU  - Jerri Nummenpalo
AU  - Alexander Pilz
AU  - Daniel Wolleb-Graf
TI  - Switches in Eulerian graphs
JO  - Acta mathematica Universitatis Comenianae
PY  - 2019
SP  - 1087
EP  - 1092
VL  - 88
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a112/
ID  - AMUC_2019_88_3_a112
ER  - 
%0 Journal Article
%A Ahad N. Zehmakan
%A Jerri Nummenpalo
%A Alexander Pilz
%A Daniel Wolleb-Graf
%A Ahad N. Zehmakan
%A Jerri Nummenpalo
%A Alexander Pilz
%A Daniel Wolleb-Graf
%T Switches in Eulerian graphs
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 1087-1092
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a112/
%F AMUC_2019_88_3_a112

Voir la notice de l'article provenant de la source Comenius University

We show that the graph transformation problem of turning a simple graph into an Eulerian one by a minimum number of single edge switches is NP-hard. Further, we show that any simple Eulerian graph can be transformed into any other such graph by a sequence of 2-switches (i.e., exchange of two edge pairs), such that every intermediate graph is also Eulerian. However, finding the shortest such sequence also turns out to be an NP-hard problem.