无限图中的无边相交链路

Edge-disjoint linkage in infinite graphs

摘要 Abstract

1980年,Thomassen提出了弱链路猜想:对于奇数正整数 \( k \),如果图 \( G \) 是 \( k \)-边连通的,则对于 \( G \) 中任意一组 \( k \) 对顶点(不一定是不同的) \(\{s_1,t_1\}, ..., \{s_k,t_k\}\),存在 \( G \) 中无边相交的路径 \( P_1, ..., P_k \),其中 \( P_i \) 连接 \( s_i \) 和 \( t_i \)。1991年,Huck证明了当 \( G \) 是有限图且 \( (k+1) \)-边连通时结论成立。我们证明了Huck定理对所有无限图也成立,推广并改进了Ok、Richter和Thomassen针对单端、局部有限图的结果。证明中一个新颖的关键工具是第3节中证明的链接扇形引理。为了展示该引理在其他上下文中的潜力和实用性,我们在最后一节给出了一项新结果,类似于Thomassen的一个结果,即在 \( (2k+2) \)-边连通的无限图中存在 \( 2k \)-边连通的有限嵌入,并由此推导出关于 \( k \)-弧连通定向的一个陈述。

In 1980, Thomassen stated his Weak Linkage conjecture: for odd positive integers $k$, if a graph $G$ is $k$-edge-connected, then, for any collection of $k$ pairs of vertices $\{s_1,t_1\}$, ..., $\{s_k,t_k\}$ in $G$, not necessarily distinct, there are pairwise edge-disjoint paths $P_1,...,P_k$ in $G$, with $P_i$ joining $s_i$ and $t_i$. In 1991, Huck proved that the conclusion holds if $G$ is finite and $(k+1)$-edge-connected. We prove that Huck's theorem holds also for all infinite graphs, extending and improving a result of Ok, Richter and Thomassen for 1-ended, locally finite graphs. A novel key tool in the proof is the Linking Fan Proposition proved in Section 3. To show the potential and usefulness of this proposition in other contexts, we present in the last section a new result, similar to a result of Thomassen, on the existence of $2k$-edge-connected finite immersions in $(2k+2)$-edge-connected infinite graphs, and as a corollary we also reprove a statement on $k$-arc-connected orientations.

无限图中的无边相交链路 - arXiv