Monotone edge flips to an orientation of maximum edge-connectivity a la Nash-Williams
Monotone edge flips to an orientation of maximum edge-connectivity a la Nash-Williams
复制标题
单调边缘翻转到最大边缘连通性的方向，如纳什-威廉姆斯
DOI：
10.1145/3561302
复制
发表时间：
2023
影响因子：
1.3
通讯作者：
Kenta Ozeki
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Yuni Iwamasa;Naonori Kakimura;Naoyuki Kamiyama;Yusuke Kobayashi;Shun-ichi Maezawa;Yuta Nozaki;Yoshio Okamoto;Kenta Ozeki
我们通过边翻转分叉≥2对无向图的K边连通方向进行了研究，证明了在无向2k边连通图的每个方向上，都存在一个边序列，使得逐个反转方向不会降低边的连通性，最终的方向是k边连通的。这给出了Nash-Williams定理的一个新证明：一个无向图G有ak个边连通的方向当且仅当Gis2k-边连通。作为该定理的另一个推论，我们证明了如果无向图G是(2k+2)-边连通的，则无向图G的K-边连通方向的边翻转图是连通的。已知只有当k=1时，这才是正确的。
We initiate the study ofk-edge-connected orientations of undirected graphs through edge flips fork≥ 2. We prove that in every orientation of an undirected2k-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 isk-edge connected. This yields an “edge-flip based” new proof of Nash-Williams’ theorem: A undirected graphGhas ak-edge-connected orientation if and only ifGis2k-edge connected. As another consequence of the theorem, we prove that the edge-flip graph ofk-edge-connected orientations of an undirected graphGis connected ifGis(2k+2)-edge connected. This has been known to be true only whenk=1.