کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4655371 1632947 2014 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Two notions of unit distance graphs
ترجمه فارسی عنوان
دو مفهوم نمودار فاصله واحد
کلمات کلیدی
نمودار فاصله واحد، نمایش گراف بعد گراف
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A faithful (unit) distance graph   in RdRd is a graph whose set of vertices is a finite subset of the d-dimensional Euclidean space, where two vertices are adjacent if and only if the Euclidean distance between them is exactly 1. A (unit) distance graph   in RdRd is any subgraph of such a graph.In the first part of the paper we focus on the differences between these two classes of graphs. In particular, we show that for any fixed d   the number of faithful distance graphs in RdRd on n   labelled vertices is 2(1+o(1))dnlog2n, and give a short proof of the known fact that the number of distance graphs in RdRd on n   labelled vertices is 2(1−1/⌊d/2⌋+o(1))n2/22(1−1/⌊d/2⌋+o(1))n2/2. We also study the behavior of several Ramsey-type quantities involving these graphs.In the second part of the paper we discuss the problem of determining the minimum possible number of edges of a graph which is not isomorphic to a faithful distance graph in RdRd.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 125, July 2014, Pages 1–17
نویسندگان
, ,