Switches in Eulerian graphs

Main Article Content

Ahad N. Zehmakan Jerri Nummenpalo Alexander Pilz Daniel Wolleb-Graf

Abstract

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.

Article Details

How to Cite
N. Zehmakan, A., Nummenpalo, J., Pilz, A., & Wolleb-Graf, D. (2019). Switches in Eulerian graphs. Acta Mathematica Universitatis Comenianae, 88(3), 1087-1092. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1176/766
Section
EUROCOMB 2019