کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419304 683778 2015 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A characterization of P5P5-free graphs with a homeomorphically irreducible spanning tree
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A characterization of P5P5-free graphs with a homeomorphically irreducible spanning tree
چکیده انگلیسی

A spanning tree with no vertices of degree two is called a homeomorphically irreducible spanning tree (or a HIST  ) of a graph. In Furuya and Tsuchiya (2003), the sets of forbidden subgraphs that imply the existence of a HIST in a connected graph of sufficiently large order were characterized. In this paper, we focus on characterizing connected P5P5-free graphs which have a HIST. As applications of our main result, we also characterize forbidden pairs that imply the existence of a HIST.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 185, 20 April 2015, Pages 71–78
نویسندگان
, , , , , , ,