The Cyclomatic Number of a Graph and its Independence Polynomial at -1

Vadim E. Levit, Eugen Mandrescu

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

4 ציטוטים ‏(Scopus)

תקציר

If by sk is denoted the number of independent sets of cardinality k in a graph G, then I(G; x) = s0 + s1x +...+ sαx α is the independence polynomial of G (Gutman and Harary in Utilitas Mathematica 24:97-106, 1983), where α = α(G) is the size of a maximum independent set. The inequality {pipe}I (G; -1){pipe} ≤ 2ν(G), where ν(G) is the cyclomatic number of G, is due to (Engström in Eur. J. Comb. 30:429-438, 2009) and (Levit and Mandrescu in Discret. Math. 311:1204-1206, 2011). For ν(G) ≤ 1 it means that I(G; -1) ∈ {-2, -1, 0, 1, 2} In this paper we prove that if G is a unicyclic well-covered graph different from C3, then I(G; -1) ∈ {-1, 0, 1}, while if G is a connected well-covered graph of girth ≥ 6, non-isomorphic to C7 or K2 (e. g., every well-covered tree ≠ K2), then I (G; -1) = 0. Further, we demonstrate that the bounds {-2ν(G), 2ν(G)} are sharp for I (G; -1), and investigate other values of I (G; -1) belonging to the interval [-2ν(G), 2ν(G)].

שפה מקוריתאנגלית
עמודים (מ-עד)259-273
מספר עמודים15
כתב עתGraphs and Combinatorics
כרך29
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - מרץ 2013

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'The Cyclomatic Number of a Graph and its Independence Polynomial at -1'. יחד הם יוצרים טביעת אצבע ייחודית.

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