کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8902784 | 1632246 | 2017 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
New graph classes characterized by weak vertex separators and two-pairs
ترجمه فارسی عنوان
کلاس های گراف جدید که توسط جدا کننده های صاف و دو جفت مشخص می شود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A set of vertices whose deletion from a graph would increase the distance between two remaining vertices is called a weak vertex separator of the graph. Two vertices form a two-pair if all chordless paths between them have length 2. I prove that every inclusion-minimal weak vertex separator of every induced subgraph of a graph G induces a complete subgraph if and only if nonadjacent vertices of induced C4 subgraphs of G always form two-pairs of G; moreover, this is also true when “complete” and C4 are replaced with “edgeless” and K4âe (â
K1,1,2). The first of the resulting new graph classes generalizes chordal graphs, and the second generalizes unichord-free graphs; they both generalize distance-hereditary graphs and geodetic graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: AKCE International Journal of Graphs and Combinatorics - Volume 14, Issue 1, April 2017, Pages 13-17
Journal: AKCE International Journal of Graphs and Combinatorics - Volume 14, Issue 1, April 2017, Pages 13-17
نویسندگان
Terry A. McKee,