Paper Info
Title
A relationship between Minors and Linkages.
Abstract
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.
Year
Venue
Keywords
2017
ARS COMBINATORIA
Minor,Linkage,k-Linked,(2, k)-Linked
Field
DocType
Volume
Discrete mathematics,Linkage (mechanical),Mathematics education,Mathematics
Journal
133
ISSN
Citations 
PageRank 
0381-7032
0
0.34
References 
Authors
0
1
Name
Order
Citations
PageRank
Fuyuan Chen100.68