کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652642 | 1632594 | 2011 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Characterizations of Graphs with Stretch Number less than 2
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Given a simple and finite connected graph G, the distance dG(u,v) is the length of the shortest (u,v)-path in G. Cicerone and Di Stefano [Graphs with bounded induced distance, Discrete Applied Mathematics 108 (2001), pp. 3–21] introduced and studied the class of k-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most k times the distance in the whole graph. In this paper we make a step forward in the study of such graphs by providing characterizations for k-distance-hereditary graphs, k>2, in terms of both forbidden subgraphs and cycle-chord conditions. Such results lead to a polynomial-time recognition algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 37, 1 August 2011, Pages 375-380
Journal: Electronic Notes in Discrete Mathematics - Volume 37, 1 August 2011, Pages 375-380