Record Details

Subdivisions of graphs: a generalization of paths and cycles

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Subdivisions of graphs: a generalization of paths and cycles
 
Creator BABU, CHSOBHAN
DIWAN, AJIT A
 
Subject graphs
graph theory
topology
hamiltonians
 
Description 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 ⪖3k and minimum degree greater-or-equal, slanted2k contains k disjoint cycles. Again, this may be restated as: every graph of order ⪖3k and minimum degree ⪖2k 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.
 
Publisher Elsevier
 
Date 2009-09-26T08:14:35Z
2011-11-25T15:38:41Z
2011-12-26T13:05:03Z
2011-12-27T05:51:00Z
2009-09-26T08:14:35Z
2011-11-25T15:38:41Z
2011-12-26T13:05:03Z
2011-12-27T05:51:00Z
2008
 
Type Article
 
Identifier Discrete Mathematics 308(19), 4479-4486
0012-365X
http://dx.doi.org/10.1016/j.disc.2007.08.045
http://hdl.handle.net/10054/1688
http://dspace.library.iitb.ac.in/xmlui/handle/10054/1688
 
Language en