|کد مقاله||کد نشریه||سال انتشار||مقاله انگلیسی||ترجمه فارسی||نسخه تمام متن|
|4949899||1364262||2017||7 صفحه PDF||سفارش دهید||دانلود کنید|
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.
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 254-260