Premium
Graph minors and linkages
Author(s) -
Chen G.,
Gould R. J.,
Kawarabayashi K.,
Pfender F.,
Wei B.
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20067
Subject(s) - combinatorics , graph minor , mathematics , line graph , graph , cubic graph , discrete mathematics , butterfly graph , voltage graph , windmill graph , distance regular graph , minor (academic) , complement graph , petersen graph , regular graph , political science , law
Bollobás and Thomason showed that every 22 k ‐connected graph is k ‐linked. Their result used a dense graph minor. In this paper, we investigate the ties between small graph minors and linkages. In particular, we show that a 6‐connected graph with a K 9 −minor is 3‐linked. Further, we show that a 7‐connected graph with a K 9 −minor is (2,5)‐linked. Finally, we show that a graph of order n and size at least 7 n −29 contains a K 9 −−minor. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 75–91, 2005