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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 6 יולי 2011

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A simple proof of an inequality connecting the alternating number of independent sets and the decycling number'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי