کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652617 | 1632594 | 2011 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Counting perfect matchings in the geometric dual
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Lovász and Plummer conjectured, in the mid 1970ʼs, that every bridgeless cubic graph has exponentially many perfect matchings. In this work we show that every cubic planar graph G whose geometric dual graph is a stack triangulation (planar 3-tree) has at least 3ϕ|V(G)|/72 distinct perfect matchings, where ϕ is the golden ratio. Our work builds on a novel approach relating Lovász and Plummerʼs claim and the number of so called groundstates of the widely studied Ising model.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 37, 1 August 2011, Pages 225-230
Journal: Electronic Notes in Discrete Mathematics - Volume 37, 1 August 2011, Pages 225-230