Alliance polynomial of regular graphs Articles uri icon

publication date

  • July 2017

start page

  • 22

end page

  • 32


  • 225

International Standard Serial Number (ISSN)

  • 0166-218X

Electronic International Standard Serial Number (EISSN)

  • 1872-6771


  • The alliance polynomial of a graph G with order n and maximum degree Delta is the polynomial A(G; x) = Sigma(Delta)(k)=-(Delta)A(k)(G) x(n+k), where A(k)(G) is the number of exact defensive k-alliances in G. We obtain some properties of A (G; x) and its coefficients for regular graphs. In particular, we characterize the degree of regular graphs by the number of non-zero coefficients of their alliance polynomial. Besides, we prove that the family of alliance polynomials of Delta-regular graphs with small degree is a very special one, since it does not contain alliance polynomials of graphs which are not Delta-regular. By using this last result and direct computation we find that the alliance polynomial determines uniquely each cubic graph of order less than or equal to 10. (C) 2017 Elsevier B.V. All rights reserved.


  • regular graphs; cubic graphs; defensive alliances; alliance polynomials