×

zbMATH — the first resource for mathematics

Highly linked graphs. (English) Zbl 0870.05044
A simple graph with at least \(2k\) vertices is called \(k\)-linked if for any choice \(s_1,\dots,s_k\), \(t_1,\dots,t_k\) of \(2k\) distinct vertices there are \(k\) vertex-disjoint paths \(p_1,\dots,p_k\) with \(p_i\) joining \(s_i\) to \(t_i\), \(1\leq i\leq k\).
Here the authors prove that if the connectivity number of \(G\) is at least \(22k\) then \(G\) is \(k\)-linked, extending ideas of N. Robertson and P. Seymour [J. Comb. Theory, Ser. B 63, No. 1, 65-110 (1995; Zbl 0823.05038)] who showed that if \(\kappa (G)\geq 10k\sqrt{\log_2 k}\) then \(G\) is \(k\)-linked.
Reviewer: M.Hager (Leonberg)

MSC:
05C40 Connectivity
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] B. Bollob?s:Extremal Graph Theory, Academic Press, London, (1978).
[2] B. Bollob?s, andA. Thomason: Topological complete subgraphs (submitted to European Journal of Combinatorics).
[3] G. A. Dirac: G?n?ralisations du th?or?me de Menger,C. R. Acad. Sci. Paris,250 (1960), 4252-4253.
[4] G. A. Dirac, andS. Schuster: A theorem of Kuratowski,Indag. Math. 16 (1954), 343-348. · Zbl 0055.17002
[5] P. Erd?s, andA. Hajnal: On topological complete subgraphs of certain graphs,Annales Univ. Sci. Budapest., (1969), 193-199.
[6] A. Huck: A sufficient condition for a graph to be weaklyk-linked,Graphs and Combinatorics,7 (1991), 323-351. · Zbl 0780.05036 · doi:10.1007/BF01787639
[7] H. A. Jung: Verallgemeinerung desn-fachen zusammenhangs f?r Graphen,Math. Ann.,187 (1970), 95-103. · Zbl 0191.22501 · doi:10.1007/BF01350174
[8] R. M. Karp: On the complexity of combinatorial problems,Networks,5 (1975), 45-68. · Zbl 0324.05003
[9] J. Koml?s, andE. Szemer?di: Topological cliques in graphs,Combinatorics, Probability and Computing,3 (1994), 247-256. · Zbl 0809.05080 · doi:10.1017/S0963548300001140
[10] J. Koml?s, andE. Szemer?di: Topological cliques in graphs II,Combinatorics, Probrability and Computing,5 (1996), 79-90. · Zbl 0846.05023 · doi:10.1017/S096354830000184X
[11] 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. · Zbl 0544.05037
[12] 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. · Zbl 0201.56801 · doi:10.1112/plms/s3-20.1.144
[13] W. Mader: Homomorphieeigenschaften und mittlere Kantendichte von Graphen,Math. Annalen,174 (1967), 265-268. · Zbl 0171.22405 · doi:10.1007/BF01364272
[14] W. Mader: Existenzn-fach zusammenh?ngender Teilgraphen in Graphen genugend grossen Kantendichte,Abh. Math. Sem Hamburg Univ.,37 (1972), 86-97. · Zbl 0215.33803 · doi:10.1007/BF02993903
[15] W. Mader: Hinreichende Bedingungen f?r die Existenz von Teilgraphen, die zu einem vollst?ndigen Graphen homomorph sind,Math. Nachr. 53 (1972), 145-150. · Zbl 0217.02504 · doi:10.1002/mana.19720530113
[16] N. Robertson, andP. Seymour: Graph Minors XIII, The disjoint paths problem,Journal of Combin. Theory, Ser. B,63 (1995), 65-100. · Zbl 0823.05038 · doi:10.1006/jctb.1995.1006
[17] P. Seymour: Disjoint paths in graphs,Discrete Math.,29 (1980) 293-309. · Zbl 0457.05043 · doi:10.1016/0012-365X(80)90158-2
[18] A. Thomason: An extremal function for complete subgraphs,Math. Proc. Camb. Phil. Soc.,95 (1984), 261-265. · Zbl 0551.05047 · doi:10.1017/S0305004100061521
[19] C. Thomassen: 2-linked graphs,Europ. J. Combinatorics,1 (1980), 371-378. · Zbl 0457.05044
[20] C. Thomassen: Highly connected non-2-linked graphs,Combinatorica,11 (1991), 393-395. · Zbl 0746.05030 · doi:10.1007/BF01275674
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.