Premium
Cycle‐minors and subdivisions of wheels
Author(s) -
Turner Galen E.
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.20393
Subject(s) - combinatorics , mathematics , subdivision , vertex (graph theory) , graph , wheel graph , graph factorization , neighbourhood (mathematics) , discrete mathematics , graph power , line graph , geography , mathematical analysis , archaeology
In this paper we prove two results. The first is an extension of a result of Dirac which says that any set of n vertices of an n ‐connected graph lies in a cycle. We prove that if V ′ is a set of at most 2 n vertices in an n ‐connected graph G , then G has, as a minor, a cycle using all of the vertices of V ′. The second result says that if G is an n +1‐connected graph with maximum vertex degree Δ then G contains a subgraph that is a subdivision of W 2 n if and only if Δ≥2 n . © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 100–108, 2009