Distinctive power of the alliance polynomial for regular graphs Article

Carballosa, W, Rodríguez, JM, Sigarreta, JM et al. (2014). Distinctive power of the alliance polynomial for regular graphs . 46(1), 313-320. 10.1016/j.endm.2014.08.041

cited authors

  • Carballosa, W; Rodríguez, JM; Sigarreta, JM; Torres-Nuñez, Y

abstract

  • The alliance polynomial of a graph G with order n and maximum degree δ is the polynomial A(G;x)=∑k=δδAk(G)xn+k, where Ak(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 δ-regular graphs with small degree is a very special one, since it does not contain alliance polynomials of graphs which are not δ-regular.

publication date

  • January 1, 2014

Digital Object Identifier (DOI)

start page

  • 313

end page

  • 320

volume

  • 46

issue

  • 1