محاسبه عدد توران زیرگراف های فراگیر اسپارس

گراف دلخواه H را در نظر بگیرید. برای این گراف فرض کنید (Δ(H ماکزیمم درجه و (δ(H مینیمم درجه گراف H باشند. ما در این مقاله ثابت می کنیم برای هر n به اندازه کافی بزرگ، اگر (فرمول در متن مقاله اصلی) باشد، در این صورت عدد اکسترمال (ex(n,H که بیان گر ماکزیمم تعداد یال یک گراف n راسی دلخواه است، که شامل هیچ زیرگراف یکریخت با H نیست، برابر با (فرمول در متن مقاله اصلی) است. شرط ماکزیمم درجه شرطی ضروری برای این م سئله است. در حقیقت روش ما در این مقاله تعمیم حالت کلاسیک نتایج اور برای (H=C(n است. همچنین در این مقاله حالت قوی تری از حدس گلی باو، پرسن، و ویپس برای گراف ها اثبات می کنیم.

کلیدواژه ها:

عدد توران ، زیرگراف فراگیر ، هم بسته ، دور همیلتنی