Levit, Vadim E.; Mandrescu, Eugen On the independence polynomial of an antiregular graph. (English) Zbl 1289.05221 Carpathian J. Math. 28, No. 2, 279-288 (2012). Summary: A graph with at most two vertices of the same degree is known as “antiregular” [R. Merris, Publ. Elektroteh. Fak., Univ. Beogr., Ser. Mat. 14, 1–3 (2003; Zbl 1088.05505)], “maximally nonregular” [A. A. Zykov, Fundamentals of graph theory. Moscow, ID: BCS Associates (1990; Zbl 0707.05001)] or “quasiperfect” [M. Behzad and G. Chartrand, Am. Math. Mon. 74, 962–963 (1967; Zbl 0179.52701)] if it has at most two vertices of the same degree. If \(s_k\) is the number of independent sets of cardinality \(k\) in a graph \(G\), then \(I(G;x)=s_0+s_1x+\dots +s_\alpha x^\alpha\) is the “independence polynomial” of \(G\) [I. Gutman and F. Harary, Util. Math. 24, 97–106 (1983; Zbl 0527.05055)], where \(\alpha=\alpha(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” [V. Chvátal and P. L. Hammer, Ann. Discrete Math. 1, 145–162 (1977; Zbl 0384.90091)]. 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\}\). Cited in 4 Documents MSC: 05C31 Graph polynomials 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) Keywords:independent set; independence polynomial; antiregular graph; threshold graph Citations:Zbl 1088.05505; Zbl 0707.05001; Zbl 0179.52701; Zbl 0527.05055; Zbl 0384.90091 PDFBibTeX XMLCite \textit{V. E. Levit} and \textit{E. Mandrescu}, Carpathian J. Math. 28, No. 2, 279--288 (2012; Zbl 1289.05221) Full Text: arXiv