Parity constrained strongly connected orientations

Definitions and mathematical statement

Let $G=(V,E)$ be a finite loopless undirected graph and $k\ge1$. For an orientation $D$, write $d_D^-(v)$ for the number of edges directed into $v$, and $\rho_D(X)$ for the number of arcs entering a vertex set $X$ from its complement. The orientation is $k$-arc-connected when \[ \rho_D(X)\ge k \quad(\varnothing\ne X\subsetneq V). \] For $k=1$ this is strong connectivity.

Characterize the graphs admitting an orientation that satisfies this cut condition and simultaneously has \[ d_D^-(v)\equiv1\pmod2 \quad(v\in V). \] Seek a useful necessary-and-sufficient criterion in the undirected graph and an effective construction for feasible inputs, including the strong-connectivity case and the higher-connectivity extension.

Necessary conditions include $2k$-edge-connectivity and $|E|\equiv |V|\pmod2$, since the sum of all indegrees is $|E|$. These elementary conditions are not asserted to be sufficient. The parity prescription applies to every vertex, while connectivity is global across every nontrivial cut. An orientation that is merely reachable from one root need not meet this requirement. Likewise, constructing an odd-indegree orientation and a strongly connected orientation separately does not ensure a single orientation meeting both demands.

Short English statement

Characterize when a graph can be oriented with odd indegree at every vertex while remaining strongly, or $k$-arc, connected.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000063 (AMR-029-0063), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Parity constrained strongly connected orientations. Original source indexed by AMR-029-0063. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Parity constrained strongly connected orientations. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Parity_constrained_strongly_connected_orientations.