תקציר
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'. יחד הם יוצרים טביעת אצבע ייחודית.פורמט ציטוט ביבליוגרפי
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver