Perfect domination polynomial of homogeneous caterpillar graphs and of full binary trees (Q2113431)

Let \(G=(V,E)\) be a simple graph of order \(n\). A set \(S\subseteq V(G)\) is a perfect dominating set of a graph \(G\) if every vertex \(v\in V(G)\setminus S\) is adjacent to exactly one vertex in \(S\). The perfect domination number \(\gamma_{pf}(G)\) is the minimal cardinality of perfect dominating sets in \(G\). Let \(D_{pf}(G, i)\) be the set of perfect dominating sets of \(G\) with cardinality \(i\) and \(d_{pf}(G, i)=|D_{pf}(G, i)|\). The perfect domination polynomial of \(G\) is defined as \(D_{pf}(G,x)=\sum_{i=\gamma_{pf}(G)}^n d_{pf}(G,i) x^i\), where \(d_{pf}(G, i)\) is the number of perfect dominating sets of \(G\) of size \(i\). In this paper, the authors determine the perfect domination polynomial of homogeneous caterpillars and of full binary trees.