Subdivisions of graphs: A generalization of paths and cycles |
| |
Authors: | Ch Sobhan Babu Ajit A Diwan |
| |
Institution: | Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India |
| |
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 ?3k and minimum degree ?2k 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. |
| |
Keywords: | Spanning subdivision Minimum degree condition Unicyclic graphs |
本文献已被 ScienceDirect 等数据库收录! |
|