کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646597 | 1342307 | 2016 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on the values of independence polynomials at −1−1
ترجمه فارسی عنوان
یادداشتی در مورد مقادیر چندجمله ای های نابستگی در -1-1
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
چند جمله ای نابستگی؛ عدد Decycling
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The independence polynomial I(G;x)I(G;x) of a graph GG is I(G;x)=∑k=0α(G)skxk, where sksk is the number of independent sets in GG of size kk. The decycling number of a graph GG, denoted ϕ(G)ϕ(G), is the minimum size of a set S⊆V(G)S⊆V(G) such that G−SG−S is acyclic. Engström proved that the independence polynomial satisfies |I(G;−1)|≤2ϕ(G)|I(G;−1)|≤2ϕ(G) for any graph GG, and this bound is best possible. Levit and Mandrescu provided an elementary proof of the bound, and in addition conjectured that for every positive integer kk and integer qq with |q|≤2k|q|≤2k, there is a connected graph GG with ϕ(G)=kϕ(G)=k and I(G;−1)=qI(G;−1)=q. In this note, we prove this conjecture.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 11, 6 November 2016, Pages 2723–2726
Journal: Discrete Mathematics - Volume 339, Issue 11, 6 November 2016, Pages 2723–2726
نویسندگان
Jonathan Cutler, Nathan Kahl,