Premium
Unavoidable parallel minors of 4‐connected graphs
Author(s) -
Chun Carolyn,
Ding Guoli,
Oporowski Bogdan,
Vertigan Dirk
Publication year - 2009
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.20361
Subject(s) - combinatorics , mathematics , zigzag , graph , discrete mathematics , partition (number theory) , wheel graph , symmetric graph , line graph , graph power , voltage graph , geometry
A parallel minor is obtained from a graph by any sequence of edge contractions and parallel edge deletions. We prove that, for any positive integer k , every internally 4‐connected graph of sufficiently high order contains a parallel minor isomorphic to a variation of K 4, k with a complete graph on the vertices of degree k , the k ‐partition triple fan with a complete graph on the vertices of degree k , the k ‐spoke double wheel, the k ‐spoke double wheel with axle, the (2k+1)‐rung Möbius zigzag ladder, the (2 k )‐rung zigzag ladder, or K k . We also find the unavoidable parallel minors of 1‐, 2‐, and 3‐connected graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 313‐326, 2009