Header menu link for other important links
X
Subdivisions of graphs: A generalization of paths and cycles
, A.A. Diwan
Published in
2008
Volume: 308
   
Issue: 19
Pages: 4479 - 4486
Abstract
One of the basic results in graph theory is Dirac's theorem, that every graph of order n ≥ 3 and minimum degree ≥ n / 2 is Hamiltonian. This may be restated as: if a graph of order n and minimum degree ≥ n / 2 contains a cycle C then it contains a spanning cycle, which is just a spanning subdivision of C. We show that the same conclusion is true if instead of C, we choose any graph H such that every connected component of H is non-trivial and contains at most one cycle. The degree bound can be improved to (n - t) / 2 if H has t components that are trees. We attempt a similar generalization of the Corrádi-Hajnal theorem that every graph of order ≥ 3 k and minimum degree ≥ 2 k contains k disjoint cycles. Again, this may be restated as: every graph of order ≥ 3 k and minimum degree ≥ 2 k contains a subdivision of kK3. We show that if H is any graph of order n with k components, each of which is a cycle or a non-trivial tree, then every graph of order ≥ n and minimum degree ≥ n - k contains a subdivision of H. © 2007 Elsevier B.V. All rights reserved.
About the journal
JournalDiscrete Mathematics
ISSN0012365X