Alliance polynomial of regular graphs

DOI10.1016/J.DAM.2017.03.016zbMATH Open1361.05067arXiv1506.06041OpenAlexW2962706509MaRDI QIDQ528552FDOQ528552

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

Publication date: 12 May 2017

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

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$.

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

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

zbMATH Keywords

cubic graphsalliance polynomialsdefensive alliancesregular graphs

Mathematics Subject Classification ID

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

Cites Work

• A Contribution to the Theory of Chromatic Polynomials
• Roots of independence polynomials of well covered graphs
• Title not available (Why is that?)
• On the theory of the matching polynomial
• Introduction to Domination Polynomial of a Graph
• Characterization of graphs using domination polynomials
• Global defensive \(k\)-alliances in graphs
• An introduction to matching polynomials
• Clique polynomials and independent set polynomials of graphs
• Global defensive alliances in graphs
• Distinctive power of the alliance polynomial for regular graphs
• Title not available (Why is that?)
• An introduction to chromatic polynomials
• The enumeration of vertex induced subgraphs with respect to the number of components
• On the location of roots of graph polynomials
• An atlas of domination polynomials of graphs of order at most six
• Title not available (Why is that?)
• Negatively curved graph and planar metrics with applications to type
• Title not available (Why is that?)
• Algebraic characterizations of graph regularity conditions
• Upper \(k\)-alliances in graphs
• Computing the hyperbolicity constant of a cubic graph
• Title not available (Why is that?)
• Partitioning a graph into offensive \(k\)-alliances
• Recurrence relations for graph polynomials on bi-iterative families of graphs

Cited In (1)

• On the differential 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)