×

An improved linear edge bound for graph linkages. (English) Zbl 1056.05091

Summary: A graph is said to be \(k\)-linked if it has at least \(2k\) vertices and for every sequence \(s_1,\dots,s_k, t_1,\dots,t_k\) of distinct vertices there exist disjoint paths \(P_1,\dots,P_k\) such that the ends of \(P_i\) are \(s_i\) and \(t_i\). B. Bollobás and A. Thomason [Combinatorica 16, 313–320 (1996; Zbl 0870.05044)] showed that if a simple graph \(G\) on \(n\) vertices is \(2k\)-connected and \(G\) has at least 11\(kn\) edges, then \(G\) is \(k\)-linked. We give a relatively simple inductive proof of the stronger statement that 8\(kn\) edges and 2\(k\)-connectivity suffice, and then with more effort improve the edge bound to \(5kn\).

MSC:

05C40 Connectivity
05C38 Paths and cycles

Keywords:

\(k\)-linked; paths

Citations:

Zbl 0870.05044
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bollobás, B.; Thomason, A., Highly linked graphs, Combinatorica, 16, 313-320 (1996) · Zbl 0870.05044
[2] Egawa, Y.; Faudree, R. J.; Györi, E.; Ishigami, Y.; Schelp, R. H.; Wang, H., Vertex-disjoint cycles containing specified edges, Graphs Combin., 16, 81-92 (2000) · Zbl 0951.05061
[3] Jung, H. A., Verallgemeinerung des n-fachen Zusammenhangs fuer graphen, Math. Ann., 187, 95-103 (1970) · Zbl 0184.27601
[4] K. Kawarabayashi, A. Kostochka, G. Yu, On sufficient degree conditions for a graph to be \(K\); K. Kawarabayashi, A. Kostochka, G. Yu, On sufficient degree conditions for a graph to be \(K\) · Zbl 1109.05061
[5] Kostochka, A., A lower bound for the hadwiger number of a graph as a function of the average degree of its vertices, Discret. Analyz, 38, 37-58 (1982), Novosibirsk · Zbl 0544.05037
[6] Larman, D. G.; Mani, P., On the existence of certain configurations within graphs and the 1-skeletons of polytopes, Proc. London Math. Soc., 20, 144-160 (1974) · Zbl 0201.56801
[7] Mader, W., Homomorphieeigenschaften und Mittlere Kantendichte von graphen, Math. Ann., 174, 265-268 (1967) · Zbl 0171.22405
[8] Robertson, N.; Seymour, P. D., Graph minors XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63, 65-110 (1995) · Zbl 0823.05038
[9] Seymour, P. D., Disjoint paths in graphs, Discrete Math., 29, 293-309 (1980) · Zbl 0457.05043
[10] Shiloach, Y., A polynomial solution to the undirected two paths problem, J. Assoc. Comp. Machinery, 27, 445-456 (1980) · Zbl 0475.68042
[11] R. Thomas, P. Wollan, The extremal function for 3-linked graphs (manuscript); R. Thomas, P. Wollan, The extremal function for 3-linked graphs (manuscript) · Zbl 1171.05030
[12] Thomason, A., An extremal function for complete subgraphs, Math. Proc. Camb. Phil. Soc., 95, 261-265 (1984) · Zbl 0551.05047
[13] Thomassen, C., 2-linked graphs, European J. Combin., 1, 371-378 (1980) · Zbl 0457.05044
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.