A simple proof of an inequality connecting the alternating number of independent sets and the decycling number

Vadim E. Levit, Eugen Mandrescu

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

7 اقتباسات (Scopus)

ملخص

If sk denotes the number of independent sets of cardinality k and α(G) is the size of a maximum independent set in graph G, then I(G;x)=s0+s1x+⋯+sα( G)xα(G) is the independence polynomial of G (Gutman and Harary, 1983) [8]. In this paper we provide an elementary proof of the inequality|I(G;-1)|≤2φ(G) (Engstrm, 2009) [7], where φ(G) is the decycling number of G (Beineke and Vandell, 1997) [3], namely, the minimum number of vertices that have to be deleted in order to turn G into a forest.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)1204-1206
عدد الصفحات3
دوريةDiscrete Mathematics
مستوى الصوت311
رقم الإصدار13
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 6 يوليو 2011

بصمة

أدرس بدقة موضوعات البحث “A simple proof of an inequality connecting the alternating number of independent sets and the decycling number'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا