On Sufficient Degree Conditions for a Graph to be $k$-linked
On Sufficient Degree Conditions for a Graph to be $k$-linked
复制标题
DOI：
10.1017/s0963548305007479
复制
发表时间：
2006-07
期刊：
影响因子：
--
通讯作者：
K. Kawarabayashi;A. Kostochka;Gexin Yu
中科院分区：
文献类型：
--
作者：
K. Kawarabayashi;A. Kostochka;Gexin Yu
一个图是k-连通的，如果对于每个2k个顶点的列表$\{s_1，{\ldots}\，s_k，t_1，{\ldots}\，t_k\}$，存在内部不相交的路$P_1，{\ldots}\，P_k$使得每个$P_i$是$s_i，t_i$-路。设$D（n，k）$是使得每一个最小度至少为$d$的$n$-顶点图是$k$-连通的最小正整数$d$，设$R（n，k）$是使得每一对不相邻顶点的度之和至少为$r$的$n$-顶点图是$k$-连通的最小正整数$r$。本文的主要结果是对每一个n和k求出了D（n，k）和R（n，k）的精确值。托马斯和Wollan [14]利用界$D（n，k）\leq（n+3 k）/2-2$给出了一个图在连通度方面是$k$-连通的充分条件。我们的界允许我们稍微修改一下Wollan证明，证明每个平均度至少为12 k的2k-连通图都是k-连通的。
A graph is $k$-linked if for every list of $2k$ vertices $\{s_1,{\ldots}\,s_k, t_1,{\ldots}\,t_k\}$, there exist internally disjoint paths $P_1,{\ldots}\, P_k$ such that each $P_i$ is an $s_i,t_i$-path. We consider degree conditions and connectivity conditions sufficient to force a graph to be $k$-linked. Let $D(n,k)$ be the minimum positive integer $d$ such that every $n$-vertex graph with minimum degree at least $d$ is $k$-linked and let $R(n,k)$ be the minimum positive integer $r$ such that every $n$-vertex graph in which the sum of degrees of each pair of non-adjacent vertices is at least $r$ is $k$-linked. The main result of the paper is finding the exact values of $D(n,k)$ and $R(n,k)$ for every $n$ and $k$. Thomas and Wollan [14] used the bound $D(n,k)\leq (n+3k)/2-2$ to give sufficient conditions for a graph to be $k$-linked in terms of connectivity. Our bound allows us to modify the Thomas–Wollan proof slightly to show that every $2k$-connected graph with average degree at least $12k$ is $k$-linked.