Switches in Eulerian graphs

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

Switches in Eulerian graphs

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

Research output: Working paper

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.

Original language	English
Publication status	Published - 2019
Externally published	Yes

Access to Document

https://dblp.org/rec/journals/corr/abs-1905-06895

Cite this

@techreport{ec102747f3b9494295f6ff2760d1f929,

title = "Switches in Eulerian graphs",

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.",

author = "Zehmakan, \{Ahad N.\} and Jerri Nummenpalo and Alexander Pilz and Daniel Wolleb-Graf",

note = "DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

year = "2019",

language = "English",

type = "WorkingPaper",

}

TY - UNPB

T1 - Switches in Eulerian graphs

AU - Zehmakan, Ahad N.

AU - Nummenpalo, Jerri

AU - Pilz, Alexander

AU - Wolleb-Graf, Daniel

N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

M3 - Working paper

BT - Switches in Eulerian graphs

ER -

Switches in Eulerian graphs

Abstract

Access to Document

Fingerprint

Cite this