کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6424238 1632784 2014 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The number of disk graphs
ترجمه فارسی عنوان
تعداد نمودارهای دیسک
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A disk graph is the intersection graph of disks in the plane, and a unit disk graph is the intersection graph of unit radius disks in the plane. We give upper and lower bounds on the number of labeled unit disk and disk graphs on n vertices. We show that the number of unit disk graphs on n vertices is n2n⋅α(n)n and the number of disk graphs on n vertices is n3n⋅β(n)n, where α(n) and β(n) are Θ(1). We conjecture that there exist constants α,β such that the number of unit disk graphs is n2n⋅(α+o(1))n and the number of disk graphs is n3n⋅(β+o(1))n.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 35, January 2014, Pages 413-431
نویسندگان
, ,