A relationship between Minors and Linkages

作者：Chen, Fuyuan^*

来源：Ars Combinatoria, 2017, 133: 317-327.

• Minor
• Linkage
• k-Linked
• (2, k)-Linked

Linkage is very important in very large scale integration (VLSI) physical design. In this paper, we mainly study the relationship between minors and linkages. Thomassen conjectured that every (2k + 2)-connected graph is k-linked. For k >= 4, K3k-1 with k disjoint edges deleted is a counterexample to this conjecture, however, it is still open for k = 3. Thomas and Wollan 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. Chen et al. 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 conclusions, improve Thomas and Wollan's results, and moreover, they give a class of graphs that satisfy Thomassen's conjecture for k = 4.

• 出版日期2017-7
• 单位安徽财经大学