کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6424408 1632801 2011 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the maximum number of cliques in a graph embedded in a surface
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the maximum number of cliques in a graph embedded in a surface
چکیده انگلیسی

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
نویسندگان
, , , , ,