Perfect domination polynomial of homogeneous caterpillar graphs and of full binary trees
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.
scientific article; zbMATH DE number 7488505
scientific article