کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647188 | 1632413 | 2014 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On embedding graphs with bounded sum of size and maximum degree
ترجمه فارسی عنوان
در تعبیه نمودارها با مجموع محدود اندازه و حداکثر درجه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودارهای جاسازی شده، نمودار بسته بندی زیرمجموعه گراف های تکمیلی،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We say that a graph is embeddable if it is a subgraph of its complement. One of the classic results on graphs embedding says that each graph on n vertices with at most nâ2 edges is embeddable. The bound on the number of edges cannot be increased because, for example, the star on n vertices is not embeddable. The reason of this fact is the existence of a vertex with very high degree. In this paper we prove that by forbidding such vertices, one can significantly increase the bound on the number of edges. Namely, we prove that if Î(G)+|E(G)|â¤2nâf(n), where f(n)=o(n), then G is embeddable. Our result is asymptotically best possible, since for the star Sn (which is not embeddable) we have Î(Sn)+|E(Sn)|=2nâ2. As a corollary, we obtain that a digraph embedding conjecture by Benhocine and Wojda (1985) is true for digraphs with sufficiently many symmetric arcs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 329, 28 August 2014, Pages 12-18
Journal: Discrete Mathematics - Volume 329, 28 August 2014, Pages 12-18
نویسندگان
Andrzej Żak,