A new method for computing domination polynomials of graphs

Authors Mohammad Reza Farahani, Hamid Hosseini

Publication date 10 November 2016

Published in Pacific Journal of Applied Mathematics (Search for Journal in Brave)

Capra-designed planar benzenoid graph domination polynomial molecular graph

Trees (05C05) Graph polynomials (05C31) Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Review text

The domination polynomial \(D(G,x)\) of a connected graph \(G\) of order \(n\) with domination number \(\gamma\) is defined by \(D(G,x)=\sum^n_\gamma d(G,i)x^i\), where \(d(G,i)\) is the number of dominating sets of \(G\) of cardinality \(i\).NEWLINENEWLINEThe primary objective of this paper is to introduce a new algorithm for calculating the domination polynomial of a graph and to then use it to calculate the domination polynomial of the molecular graph Capra-designed planar benzenoid. The authors comment that classical methods used on this graph are complex, difficult to understand and slow to run.NEWLINENEWLINEAlthough the writing in this paper is sometimes difficult to follow (I assume that English is not the first language of the authors), and there are some technical issues like missing definitions of notation, this is an interesting paper, especially for those of us looking for real-life applications of graph theory in other fields.

Recommendations

Cited in

(7)

This page was built for publication: A new method for computing domination polynomials of graphs

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