authors
- CARBALLOSA TORRES, WALTER
- RODRIGUEZ GARCIA, JOSE MANUEL
- SIGARRETA ALMIRA, JOSE MARIA
- TORRES NUÑEZ, YADIRA
Computing the alliance polynomial of a graph
Articles
Overview
published in
- ArXiv.org Journal
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.