TR-2006-01

Reliable Orientations of Eulerian Graphs

Zoltán Király, Zoltán Szigeti



Abstract

We present a characterization of Eulerian graphs that have a k-arc-connected orientation so that the deletion of any vertex results in a (k-1)-arc-connected directed graph. This provides an affirmative answer for a conjecture of Frank. The special case, when k=2, describes Eulerian graphs admitting 2-vertex-connected orientations. This case was proved earlier by Berg and Jordán. These results are specializations of the related results from [5].


Bibtex entry:

@techreport{egres-06-01,
AUTHOR = {Kir{\'a}ly, Zolt{\'a}n and Szigeti, Zolt{\'a}n},
TITLE = {Reliable Orientations of Eulerian Graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2006},
NUMBER = {TR-2006-01}
}


Last modification: 9.1.2018. Please email your comments to Tamás Király!