On the Independence Polynomial of an Antiregular Graph

Vadim E. LevitEugen Mândrescu



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], maximally 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 sk is 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, 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}.

Additional Information


Levit, Vadim E., Mândrescu, Eugen