Switches in Eulerian graphs

05/08/2019
by   Ahad N. Zehmakan, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset