کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903503 1632569 2017 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Transversals of Longest Paths
ترجمه فارسی عنوان
زوایای طولانی ترین مسیرها
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let lpt(G) be the minimum cardinality of a set of vertices that intersects all longest paths in a connected graph G. We show that, if G is a chordal graph, then lpt(G)≤max⁡{1,ω(G)−2}, where ω(G) is the size of a largest clique in G; that lpt(G)≤tw(G), where tw(G) is the treewidth of G; and that lpt(G)=1 if G is a bipartite permutation graph or a full substar graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 135-140
نویسندگان
, , , , ,