Computing the alliance polynomial of a graph Articles uri icon

publication date

  • October 2014

start page

  • 1

end page

  • 16

international standard serial number (ISSN)

  • WWWW-0074

abstract

  • Ref.: arXiv:1410.2940 [math.CO] -- Abstract: The alliance polynomial of a graph Gamma with order n and maximum degree delta1 is the polynomial A(Gamma;x)=∑┉k=−┉Ak(Gamma)xn+k, where Ak(Gamma) is the number of exact defensive k-alliances in Gamma. We provide an algorithm for computing the alliance polynomial. Furthermore, we obtain some properties of A(Gamma;x) and its coefficients. In particular, we prove that the path, cycle, complete and star graphs are characterized by their alliance polynomials. We also show that the alliance polynomial characterizes many graphs that are not distinguished by other usual polynomials of graphs.