Alliance polynomial of regular graphs

作者：Carballosa Walter; Rodriguez Jose M^*; Sigarreta Jose M; Torres Nunez Yadira

来源：Discrete Applied Mathematics, 2017, 225: 22-32.

DOI：10.1016/j.dam.2017.03.016

• Regular graphs
• Cubic graphs
• Defensive alliances
• Alliance polynomials

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.

• 出版日期2017-7-10