Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams

Autor:	Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-Ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
Rok vydání:	2023
Předmět:	Mathematics (miscellaneous) Computer Science - Data Structures and Algorithms Mathematics - Combinatorics MathematicsofComputing_DISCRETEMATHEMATICS Computer Science - Discrete Mathematics
Zdroj:	ACM Transactions on Algorithms. 19:1-22
ISSN:	1549-6333 1549-6325
Popis:	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: A 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 .
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::091269ec193a84decaffaf7a8ef858db https://doi.org/10.1145/3561302 Zobrazit plný text záznamu