Parity constrained strongly connected orientations
Find a good characterization for undirected graphs having a strongly connected (more generally k-edge-connected) orientation so that the in-degree of every node is odd.
Remarks
The analogous problem with rooted k-edge-connectivity requirement was solved by Frank, Jordán and Szigeti [1]. However, the natural extension of their characterization to the strongly connected case is not sufficient, as shown by an example by T. Király and Szabó [2].
Frank and Z. Király [3] characterized graphs which admit a T-odd and k-edge-connected orientation for every possible choice of subsets [math] T \subseteq V[/math] with [math]\vert E\vert+\vert T\vert[/math] even (an orientation is T-odd if a node has odd in-degree if and only if it is in T). A similar characterization for rooted k-edge-connectivity follows easily from the results in [1].
References
- ↑ 1.0 1.1 A. Frank, T. Jordán, Z. Szigeti, An orientation theorem with parity conditions, Discrete Applied Mathematics 115 (2001) 37--45. DOI link
- ↑ T. Király, J. Szabó, A note on parity constrained orientations, DOI link, EGRES Technical Report no. 2003-11
- ↑ A. Frank, Z. Király, Graph orientations with edge-connection and parity constraints, Combinatorica 22 (2002), 47--70. DOI link
