On the independence polynomial of an antiregular graph

Details On the independence polynomial of an antiregular graph On the independence polynomial of an antiregular graph

2010-07-06

arxiv.org/abs/1007.0880v1

Computer Science

Discrete Mathematics

11 pages, 5 figures

Scientific paper

A graph with at most two vertices of the same degree is called antiregular (Merris 2003), maximally nonregular (Zykov 1990) or quasiperfect (Behzad, Chartrand 1967). If s_{k} is the number of independent sets of cardinality k in a graph G, then I(G;x) = s_{0} + s_{1}x + ... + s_{alpha}x^{alpha} is the independence polynomial of G (Gutman, Harary 1983), where alpha = alpha(G) is the size of a maximum independent set. In this paper we derive closed formulae for the independence polynomials of antiregular graphs. In particular, we deduce that every antiregular graph A is uniquely defined by its independence polynomial I(A;x), within the family of threshold graphs. Moreover, I(A;x) is logconcave with at most two real roots, and I(A;-1) belongs to {-1,0}.

Affiliated with

Also associated with

No associations

Rating

On the independence polynomial of an antiregular graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the independence polynomial of an antiregular graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the independence polynomial of an antiregular graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-216678