کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648471 | 1632431 | 2011 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Helly theorems for 3-Steiner and 3-monophonic convexity in graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Helly theorems for 3-Steiner and 3-monophonic convexity in graphs Helly theorems for 3-Steiner and 3-monophonic convexity in graphs](/preview/png/4648471.png)
چکیده انگلیسی
In this paper the Helly property of families of convex sets relative to two new graph convexities are studied. Let G be a (finite) connected graph and U a set of vertices of G. A connected subgraph with the fewest edges containing U is called a Steiner tree for U, and the collection of all vertices of G that belong to some Steiner tree for U is called the Steiner interval for U. A set S of vertices of G is g3-convex if it contains the Steiner interval for every 3-subset U of S. A subtree T of G that contains U is a minimal U-tree if every vertex of T that is not in U is a cut-vertex of the subgraph induced by V(T). The set of all vertices that belong to some minimal U-tree is called the monophonic interval for U and a set S of vertices is m3-convex if it contains the monophonic interval of every 3-subset U of S. Those graphs are characterized for which the families of g3-convex (m3-convex) sets of size at least 3 have the Helly property. A graph obtained from a complete graph by deleting a matching is called a near-clique. The maximum order of a near-clique in a graph G is called the near-clique number of G. The near-clique number of a graph is a lower bound on the Helly number for both g3-convex families and m3-convex families. For m3-convex families equality holds. For g3-convex families equality holds for chordal graphs and for distance-hereditary graphs, but the bound can be arbitrarily bad in general, even when the near-clique number is 3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issues 10â11, 6 June 2011, Pages 872-880
Journal: Discrete Mathematics - Volume 311, Issues 10â11, 6 June 2011, Pages 872-880
نویسندگان
Morten H. Nielsen, Ortrud R. Oellermann,