×

On the independence polynomial of an antiregular graph. (English) Zbl 1289.05221

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\}\).

MSC:

05C31 Graph polynomials
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: arXiv