Abstract
A graph with at least 2k vertices is said to bek-linked if, for any choices 1,...,s k ,t 1,...,t k of 2k distinct vertices there are vertex disjoint pathsP 1,...,P k withP i joinings i tot i , 1≤i≤k. Recently Robertson and Seymour [16] showed that a graphG isk-linked provided its vertex connectivityk(G) exceeds\(10k\sqrt {\log _2 k}\). We show here thatk(G)≥22k will do.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
B. Bollobás:Extremal Graph Theory, Academic Press, London, (1978).
B. Bollobás, andA. Thomason: Topological complete subgraphs (submitted to European Journal of Combinatorics).
G. A. Dirac: Généralisations du théorème de Menger,C. R. Acad. Sci. Paris,250 (1960), 4252–4253.
G. A. Dirac, andS. Schuster: A theorem of Kuratowski,Indag. Math. 16 (1954), 343–348.
P. Erdős, andA. Hajnal: On topological complete subgraphs of certain graphs,Annales Univ. Sci. Budapest., (1969), 193–199.
A. Huck: A sufficient condition for a graph to be weaklyk-linked,Graphs and Combinatorics,7 (1991), 323–351.
H. A. Jung: Verallgemeinerung desn-fachen zusammenhangs für Graphen,Math. Ann.,187 (1970), 95–103.
R. M. Karp: On the complexity of combinatorial problems,Networks,5 (1975), 45–68.
J. Komlós, andE. Szemerédi: Topological cliques in graphs,Combinatorics, Probability and Computing,3 (1994), 247–256.
J. Komlós, andE. Szemerédi: Topological cliques in graphs II,Combinatorics, Probrability and Computing,5 (1996), 79–90.
A. Kostochka: A lower bound for the Hadwiger number of a graph as a function of the average degree of its vertices,Discret. Analyz, Novosibirsk,38 (1982), 37–58.
D. G. Larman, andP. Mani: On the existence of certain configurations within graphs and the 1-skeletons of polytopes,Proc. London Math. Soc.,20 (1974), 144–160.
W. Mader: Homomorphieeigenschaften und mittlere Kantendichte von Graphen,Math. Annalen,174 (1967), 265–268.
W. Mader: Existenzn-fach zusammenhängender Teilgraphen in Graphen genugend grossen Kantendichte,Abh. Math. Sem Hamburg Univ.,37 (1972), 86–97.
W. Mader: Hinreichende Bedingungen für die Existenz von Teilgraphen, die zu einem vollständigen Graphen homomorph sind,Math. Nachr. 53 (1972), 145–150.
N. Robertson, andP. Seymour: Graph Minors XIII, The disjoint paths problem,Journal of Combin. Theory, Ser. B,63 (1995), 65–100.
P. Seymour: Disjoint paths in graphs,Discrete Math.,29 (1980) 293–309.
A. Thomason: An extremal function for complete subgraphs,Math. Proc. Camb. Phil. Soc.,95 (1984), 261–265.
C. Thomassen: 2-linked graphs,Europ. J. Combinatorics,1 (1980), 371–378.
C. Thomassen: Highly connected non-2-linked graphs,Combinatorica,11 (1991), 393–395.