%A N. Zehmakan, Ahad
%A Nummenpalo, Jerri
%A Pilz, Alexander
%A Wolleb-Graf, Daniel
%D 2019
%T Switches in Eulerian graphs
%K
%X 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.
%U http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1176
%J Acta Mathematica Universitatis Comenianae
%0 Journal Article
%P 1087-1092%V 88
%N 3
%@ 0862-9544
%8 2019-07-31