Alliance polynomial of regular graphs

DOI10.1016/J.DAM.2017.03.016MaRDI QIDQ528552zbMATHOpenAlexFDO

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

Publication date 12 May 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cubic graphsalliance polynomialsdefensive alliancesregular graphs

Mathematics Subject Classification ID

Graph polynomials (05C31) Vertex degrees (05C07)

Abstract: The alliance polynomial of a graph $G$ with order $n$ and maximum degree $Delta$ is the polynomial $A(G;x)=su{m}_{k=-Delta}^{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$.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3836093 (Why is no real title available?)
• scientific article; zbMATH DE number 2038883 (Why is no real title available?)
• scientific article; zbMATH DE number 2076807 (Why is no real title available?)
• scientific article; zbMATH DE number 2104820 (Why is no real title available?)
• A Contribution to the Theory of Chromatic Polynomials
• Algebraic characterizations of graph regularity conditions
• An introduction to chromatic polynomials
• An introduction to matching polynomials
• Characterization of graphs using domination polynomials
• Clique polynomials and independent set polynomials of graphs
• Computing the hyperbolicity constant of a cubic graph
• Computing the strong alliance polynomial of a graph
• Distinctive power of the alliance polynomial for regular graphs
• Domination polynomials of cubic graphs of order 10
• Global defensive \(k\)-alliances in graphs
• Global defensive alliances in graphs
• Introduction to domination polynomial of a graph.
• Negatively curved graph and planar metrics with applications to type
• On the location of roots of graph polynomials
• On the theory of the matching polynomial
• Partitioning a graph into offensive \(k\)-alliances
• Recurrence relations for graph polynomials on bi-iterative families of graphs
• Roots of independence polynomials of well covered graphs
• The enumeration of vertex induced subgraphs with respect to the number of components
• Upper \(k\)-alliances in graphs

Cited in

(4)

• Distinctive power of the alliance polynomial for regular graphs
• Computing the strong alliance polynomial of a graph
• On the differential polynomial of a graph
• Computing the alliance polynomial of a graph.

This page was built for publication: Alliance polynomial of regular graphs

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