×

A relationship between minors and linkages. (English) Zbl 1424.05275

Summary: Linkage is very important in very large scale integration (VLSI) physical design. In this paper, we mainly study the relationship between minors and linkages. C. Thomassen [Eur. J. Comb. 1, 371–378 (1980; Zbl 0457.05044)] conjectured that every \((2k+2)\)-connected graph is \(k\)-linked. For \(k\geq 4\), \(K_{3k-1}\) with \(k\) disjoint edges deleted is a counterexample to this conjecture, however, it is still open for \(k=3\). R. Thomas and P. Wollan [J. Comb. Theory, Ser. B 98, No. 5, 939–971 (2008)] proved that every \(6\)-connected graph on \(n\) vertices with \(5n-14\) edges is \(3\)-linked. Hence they obtain that every \(10\)-connected graph is \(3\)-linked. G. Chen et al. [J. Graph Theory 49, No. 1, 75–91 (2005; Zbl 1067.05072)] showed that every \(6\)-connected graph with \(K_9^-\) as a minor is \(3\)-linked, and every \(7\)-connected graph with \(K_9^-\) as a minor is \((2,5)\)-linked. Using a similar method, we prove that every \(8\)-connected graph with \(K_{12}^-\) as a minor is \(4\)-linked, and every \((2k+1)\)-connected graph with \(K_{2k+3}^-\) as a minor is \((2,2k-1)\)-linked. Our results extend Chen et al.’s [loc. cit.] conclusions, improve Thomas and Wollan’s [loc. cit.] results, and moreover, they give a class of graphs that satisfy Thomassen’s [loc. cit.] conjecture for \(k=4\).

MSC:

05C83 Graph minors
05C40 Connectivity
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)