ABSTRACT

This chapter describes alliance polynomial of a graph with special attention to its distinguishable power. The main contribution of this chapter is to prove that several well-known classes of graphs are characterized by the alliance polynomial. Though the alliance polynomial does not solve the characterization problem completely, it does a better job toward its solution, that is, two nonisomorphic graphs have different polynomials for a large class of graphs. The chapter computes the alliance polynomial for some graphs and study its coefficients. It proves that the path, cycle, complete, complete without one edge, and star graphs are characterized by the alliance polynomial. The chapter obtains additional results on the alliance polynomial of regular graphs, since they are also a very interesting class of graphs. It suggests that the family of alliance polynomials of connected Δ-regular graphs with small degree is a very special one, since it does not contain alliance polynomials of graphs which are not connected Δ-regular for Δ≤5.