2021/10/22 by Takehiro Ito, Ito, Takehiro, Yuni Iwamasa +15 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2110.11585
openalex publication_date 2021/10/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We initiate the study of k-edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2k-edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge-connectivity, and the final orientation is k-edge-connected. This yields an ``edge-flip based'' new proof of Nash-Williams' theorem: an undirected graph G has a k-edge-connected orientation if and only if G is 2k-edge-connected. As another consequence of the theorem, we prove that the edge-flip graph of k-edge-connected orientations of an undirected graph G is connected if G is (2k+2)-edge-connected. This has been known to be true only when k=1.