کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419303 683778 2015 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Graph metric with no proper inclusion between lines
ترجمه فارسی عنوان
نمودار متریک بدون دخالت مناسب بین خطوط
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

In trying to generalize the classic Sylvester–Gallai theorem and De Bruijn–Erdős theorem in plane geometry, lines and closure lines were previously defined for metric spaces and hypergraphs. Both definitions do not obey the geometric intuition in the sense that two lines (closure lines) may intersect at more than one point, and one line (closure line) might be the proper subset of another. In this work, we study the systems where one or both of the configurations are forbidden. We note that when any two lines intersect in at most one point, the two classic theorems extend in any metric space. We study the metric spaces induced by simple graphs where no line is a proper subset of another, and show that the least number of lines for such a graph with nn vertices is between the order of n4/3n4/3 and n4/3ln2/3nn4/3ln2/3n.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 185, 20 April 2015, Pages 59–70
نویسندگان
, , , ,