کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420945 | 684008 | 2007 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bipartite multigraphs with expander-like properties
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
This note considers the following combinatorial question: “For which integers dd and functions fdfd does there exist, for every large enough vv, a bipartite dd-regular multigraph on 2v2v nodes with node sets VV and WW having the following property: For every UU that is a subset of either VV or WW, the cardinality of the set of neighbours of UU is at least fd(|U|)fd(|U|)?” Graphs with the above property seem to behave well also with respect to other, more complicated, expander-like properties. We provide results for dd in {5,6,7,8} and give a description of a fairly general methodology for devising computer-assisted proofs for a wide class of mathematical claims using interval arithmetic.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 155, Issue 13, 15 August 2007, Pages 1667–1677
Journal: Discrete Applied Mathematics - Volume 155, Issue 13, 15 August 2007, Pages 1667–1677
نویسندگان
Lars Engebretsen,