Graph minors and linkages | Zendy

Chen G. | Zendy; Gould R. J. | Zendy; Kawarabayashi K. | Zendy; Pfender F. | Zendy; Wei B. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research