کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4949899 1364262 2017 7 صفحه PDF سفارش دهید دانلود کنید
عنوان انگلیسی مقاله ISI
Reconstructing trees from digitally convex sets
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Reconstructing trees from digitally convex sets
چکیده انگلیسی

Suppose V is a finite set and C a collection of subsets of V that contains 0̸ and V and is closed under taking intersections. Then C is called a convexity and the ordered pair (V,C) is called an aligned space and the elements of C are referred to as convex sets. For a set S⊆V, the convex hull of S relative to C, denoted by CHC(S), is the smallest convex set containing S. A set S of vertices in a graph G with vertex set V is digitally convex if for every vertex v∈V, N[v]⊆N[S] implies v∈S. It is shown that every tree is uniquely determined by its digitally convex sets. These ideas can be used to show that every graph with girth at least 7 is uniquely determined by its digitally convex sets. Given the digitally convex sets of a graph it can be determined efficiently, as a function of the number of convex sets, if these are those of a tree.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 254-260
نویسندگان
, , ,