کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649828 1342467 2009 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Collapsible graphs and reductions of line graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Collapsible graphs and reductions of line graphs
چکیده انگلیسی

A graph GG is collapsible if for every even subset X⊆V(G)X⊆V(G), GG has a subgraph ΓΓ such that G−E(Γ)G−E(Γ) is connected and the set of odd-degree vertices of ΓΓ is XX. A graph obtained by contracting all the non-trivial collapsible subgraphs of GG is called the reduction of GG. In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. Lai, Reduced graph of diameter two, J. Graph Theory 14 (1) (1990) 77–87], and in [P.A. Catlin, Iqblunnisa, T.N. Janakiraman, N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347–364].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 10, 28 May 2009, Pages 3173–3184
نویسندگان
, , ,