דילוג לניווט ראשי דילוג לחיפוש דילוג לתוכן הראשי

On the independence polynomial of an antiregular graph

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

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

תקציר

A graph with at most two vertices of the same degree is known as antiregular [Merris, R., Antiregular graphs are universal for trees, Publ. Electrotehn. Fak. Univ. Beograd, Ser. Mat. 14 (2003) 1-3], aximally nonregular [Zykov, A. A., Fundamentals of graph theory, BCS Associates, Moscow, 1990] or quasiperfect [Behzad, M. and Chartrand, D. M., No graph is perfect, Amer. Math. Monthly 74 (1967), 962-963]. If s k is the number of independent sets of cardinality k in a graph G, then I(G; x) = s 0 + s 1x +...+ s αx α is the independence polynomial of G [Gutman, I. and Harary, F., Generalizations of the matching polynomial, Utilitas Mathematica 24 (1983), 97-106], where α = α (G) is the size of a maximum independent set. In this paper we derive closed formulas for the independence polynomials of antiregular graphs. It results in proving that every antiregular graph is uniquely defined by its independence polynomial within the family of threshold graphs. Moreover, the independence polynomial of each antiregular graph is log-concave, it has two real roots at most, and its value at -1 belongs to {-1, 0}.

שפה מקוריתאנגלית
עמודים (מ-עד)279-288
מספר עמודים10
כתב עתCarpathian Journal of Mathematics
כרך28
מספר גיליון2
סטטוס פרסוםפורסם - 2012

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On the independence polynomial of an antiregular graph'. יחד הם יוצרים טביעת אצבע ייחודית.

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