Defensive alliance polynomial

MaRDI QIDQ4995282zbMATH OpenFDO

Authors H. Ibrahim

Publication date 23 June 2021

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

zbMATH Keywords

bivariate polynomialcomplete bipartite graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We introduce a new bivariate polynomial which we call the defensive alliance polynomial and denote it by da(G; x, y). It is a generalization of the alliance polynomial [Carballosa et al., 2014] and the strong alliance polynomial [Carballosa et al., 2016]. We show the relation between da(G; x, y) and the alliance, the strong alliance and the induced connected subgraph [Tittmann et al., 2011] polynomials. Then, we investigate information encoded in da(G; x, y) about G. We discuss the defensive alliance polynomial for the path graphs, the cycle graphs, the star graphs, the double star graphs, the complete graphs, the complete bipartite graphs, the regular graphs, the wheel graphs, the open wheel graphs, the friendship graphs, the triangular book graphs and the quadrilateral book graphs. Also, we prove that the above classes of graphs are characterized by its defensive alliance polynomial. A relation between induced subgraphs with order three and both subgraphs with order three and size three and two respectively, is proved to characterize the complete bipartite graphs. Finally, we present the defensive alliance polynomial of the graph formed by attaching a vertex to a complete graph. We show two pairs of graphs which are not characterized by the alliance polynomial but characterized by the defensive alliance polynomial.

Recommendations

• Defensive alliances in graphs
• On defensive alliances and line graphs
• Defensive alliances with prescribed and proscribed vertices
• Defensive k-alliances in graphs
• On the defensive alliances in graph
• Global defensive alliances in graphs
• scientific article; zbMATH DE number 6475954
• Parameterized intractability of defensive alliance problem
• On defensive alliance in zero-divisor graphs
• Global defensive alliances in the lexicographic product of paths and cycles

Cited in

(4)

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

This page was built for publication: Defensive alliance polynomial

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