کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6424408 | 1632801 | 2011 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the maximum number of cliques in a graph embedded in a surface
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
This paper studies the following question: given a surface Σ and an integer n, what is the maximum number of cliques in an n-vertex graph embeddable in Σ? We characterise the extremal graphs for this question, and prove that the answer is between 8(nâÏ)+2Ï and 8n+522Ï+o(2Ï), where Ï is the maximum integer such that the complete graph KÏ embeds in Σ. For the surfaces S0, S1, S2, N1, N2, N3 and N4 we establish an exact answer.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 32, Issue 8, November 2011, Pages 1244-1252
Journal: European Journal of Combinatorics - Volume 32, Issue 8, November 2011, Pages 1244-1252
نویسندگان
Vida DujmoviÄ, GaÅ¡per Fijavž, Gwenaël Joret, Thom Sulanke, David R. Wood,