Computing the alliance polynomial of a graph.

MaRDI QIDQ3134315zbMATH OpenFDO

Authors Walter Carballosa, José M. Rodríguez, Yadira Torres-Nuñez, Jose M. Sigarreta

Publication date 9 February 2018

Full work available at URL https://arxiv.org/abs/1410.2940

zbMATH Keywords

alliance polynomialsdefensive alliancesfinite graphs

Mathematics Subject Classification ID

Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Special sequences and polynomials (11B83)

Abstract: The alliance polynomial of a graph $Gamma$ with order $n$ and maximum degree $delt{a}_1$ is the polynomial $A(Gamma;x)=su{m}_{k=-delt{a}_1}^{delt{a}_1}{A}_k(Gamma),x^{n+k}$, where $A_k(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.

Recommendations

• Computing the strong alliance polynomial of a graph
• Distinctive power of the alliance polynomial for regular graphs
• Alliance polynomial of regular graphs
• Defensive alliance polynomial
• scientific article; zbMATH DE number 2104820

Cited in

(6)

• On the differential polynomial of a graph
• Distinctive power of the alliance polynomial for regular graphs
• Alliances and Related Domination Parameters
• Computing the strong alliance polynomial of a graph
• Alliance polynomial of regular graphs
• Distribution of the null coefficients of the differential polynomial of the tree graphs

This page was built for publication: Computing the alliance polynomial of a graph.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3134315)