## Abstract

A graph is k-linked if for every list of 2k vertices {s_{1},..., s_{k},t_{1},..,t_{k}}, there exist internally disjoint paths P_{1},...,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) ≤ (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.

Original language | English (US) |
---|---|

Pages (from-to) | 685-694 |

Number of pages | 10 |

Journal | Combinatorics Probability and Computing |

Volume | 15 |

Issue number | 5 |

DOIs | |

State | Published - Sep 2006 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics