کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650436 1342487 2008 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Subdivisions of graphs: A generalization of paths and cycles
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Subdivisions of graphs: A generalization of paths and cycles
چکیده انگلیسی

One of the basic results in graph theory is Dirac's theorem, that every graph of order n⩾3n⩾3 and minimum degree ⩾n/2⩾n/2 is Hamiltonian. This may be restated as: if a graph of order n   and minimum degree ⩾n/2⩾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(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⩾3k and minimum degree ⩾2k⩾2k contains k   disjoint cycles. Again, this may be restated as: every graph of order ⩾3k⩾3k and minimum degree ⩾2k⩾2k contains a subdivision of kK3kK3. 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⩾n and minimum degree ⩾n-k⩾n-k contains a subdivision of H.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 19, 6 October 2008, Pages 4479–4486
نویسندگان
, ,