کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656782 1632980 2015 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Linear embeddings of graphs and graph limits
ترجمه فارسی عنوان
جایگذاری خطی گرافها و محدودیتهای گراف
کلمات کلیدی
محدودیت های گراف نمودارهای فاصله، تعبیه خطی، نمودار تصادفی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Consider a random graph process where vertices are chosen from the interval [0,1][0,1], and edges are chosen independently at random, but so that, for a given vertex x, the probability that there is an edge to a vertex y decreases as the distance between x and y increases. We call this a random graph with a linear embedding.We define a new graph parameter Γ⁎Γ⁎, which aims to measure the similarity of the graph to an instance of a random graph with a linear embedding. For a graph G  , Γ⁎(G)=0Γ⁎(G)=0 if and only if G is a unit interval graph, and thus a deterministic example of a graph with a linear embedding.We show that the behaviour of Γ⁎Γ⁎ is consistent with the notion of convergence as defined in the theory of dense graph limits. In this theory, graph sequences converge to a symmetric, measurable function on [0,1]2[0,1]2. We define an operator Γ which applies to graph limits, and which assumes the value zero precisely for graph limits that have a linear embedding. We show that, if a graph sequence {Gn}{Gn} converges to a function w  , then {Γ⁎(Gn)}{Γ⁎(Gn)} converges as well. Moreover, there exists a function w⁎w⁎ arbitrarily close to w   under the box distance, so that limn→∞⁡Γ⁎(Gn)limn→∞⁡Γ⁎(Gn) is arbitrarily close to Γ(w⁎)Γ(w⁎).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 113, July 2015, Pages 162–184
نویسندگان
, , , , ,