کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657390 1343735 2006 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The circumference of a graph with no K3,t-minor
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The circumference of a graph with no K3,t-minor
چکیده انگلیسی

It was shown by Chen and Yu that every 3-connected planar graph G contains a cycle of length at least |G|log32, where |G| denotes the number of vertices of G. Thomas made a conjecture in a more general setting: there exists a function β(t)>0 for t⩾3, such that every 3-connected graph G with no K3,t-minor, t⩾3, contains a cycle of length at least |G|β(t). We prove that this conjecture is true with β(t)=log8tt+12. We also show that every 2-connected graph with no K2,t-minor, t⩾3, contains a cycle of length at least |G|/tt−1.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 96, Issue 6, November 2006, Pages 822-845