𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graph minors and linkages

✍ Scribed by G. Chen; R. J. Gould; K. Kawarabayashi; F. Pfender; B. Wei

Book ID
102343553
Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
157 KB
Volume
49
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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 minor is 3‐linked. Further, we show that a 7‐connected graph with a K minor is (2,5)‐linked. Finally, we show that a graph of order n and size at least 7__n__−29 contains a K minor. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 75–91, 2005

📜 SIMILAR VOLUMES

On graph contractions and induced minors
On graph contractions and induced minors
✍ Pim van ’t Hof; Marcin Kamiński; Daniël Paulusma; Stefan Szeider; Dimitrios M. T 📂 Article 📅 2012 🏛 Elsevier Science 🌐 English ⚖ 386 KB
Connectivity, graph minors, and subgraph
Connectivity, graph minors, and subgraph multiplicity
✍ David Eppstein 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 435 KB

## Abstract It is well known that any planar graph contains at most __O__(__n__) complete subgraphs. We extend this to an exact characterization: __G__ occurs __O__(__n__) times as a subgraph of any planar graph, if and only if __G__ is three‐connected. We generalize these results to similarly char

Graph Minors and Reliable Single Message
Graph Minors and Reliable Single Message Transmission
✍ Fich, Faith Ellen; Kündgen, André; Pelsmajer, Michael J.; Ramamurthi, Radhika 📂 Article 📅 2005 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 370 KB