کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430921 688233 2012 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On a conjecture of Erdős for multiplicities of cliques
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On a conjecture of Erdős for multiplicities of cliques
چکیده انگلیسی

Denote by kt(G)kt(G) the number of cliques of order t in a graph G having n   vertices. Let kt(n)=min{kt(G)+kt(G¯)} where G¯ denotes the complement of G  . Let ct(n)=kt(n)/(nt) and ctct be the limit of ct(n)ct(n) for n   going to infinity. A 1962 conjecture of Erdős stating that ct=21−(t2) was disproved by Thomason in 1989 for all t⩾4t⩾4. Tighter counterexamples have been constructed by Jagger, Šťovíček and Thomason in 1996, by Thomason for t⩽6t⩽6 in 1997, and by Franek for t=6t=6 in 2002. We investigate a computational framework to search for tighter upper bounds for small t   and provide the following improved upper bounds for t=6,7t=6,7 and 8: c6⩽0.7445×21−(62), c7⩽0.6869×21−(72), and c8⩽0.7002×21−(82). The constructions are based on a large but highly regular variant of Cayley graphs for which the number of cliques and cocliques can be expressed in closed form. Note that if we consider the quantity et=2(t2)−1ct, the new upper bound of 0.687 for e7e7 is the first bound for any etet smaller than the lower bound of 0.695 for e4e4 due to Giraud in 1979.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 17, December 2012, Pages 9–14
نویسندگان
, , ,