Volltext-Downloads (blau) und Frontdoor-Views (grau)

Defensive alliance polynomial

  • In this master thesis, we define 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 and the strong alliance polynomial. We show the relation between da(G; x; y) and the alliance, the strong alliance, the induced connected subgraph polynomials as well as the cut vertex sets polynomial. We investigate information encoded about G in da(G; x; y). 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. We present the defensive alliance polynomial of the graph formed of 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. Also, we present three notes on results in the literature. The first one is improving a bound and the other two are counterexamples.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar


Author:Hany Ibrahim
Advisor:Peter Tittmann, Klaus Dohmen
Document Type:Master's Thesis
Year of Completion:2018
Granting Institution:Hochschule Mittweida
Release Date:2020/03/12
GND Keyword:Polynom; Graphentheorie
Institutes:Angewandte Computer‐ und Bio­wissen­schaften
Dewey Decimal Classification:511.5 Graphentheorie
Open Access:Frei zugänglich
Licence (German):License LogoEs gilt das UrhG