# zbMATH — the first resource for mathematics

The vertex domination polynomial and edge domination polynomial of a graph. (English) Zbl 1274.05230
Summary: Let $$G$$ be a simple graph of order $$n$$, the vertex domination polynomial of $$G$$ is the polynomial $$D_0(G,x)=\sum_{i=\gamma_0 (G)}^n d_0(G,i)x^i$$, where $$d_0(G,i)$$ is the number of vertex dominating sets of $$G$$ with size $$i$$, and $$\gamma_0(G)$$ is the vertex domination number of $$G$$. Similarly, the edge domination polynomial of $$G$$ is the polynomial $$D_1(G,x)=\sum_{i=\gamma_1 (G)}^{| E(G)|} d_1(G,i)x^i$$, where $$d_1(G,i)$$ is the number of edge dominating sets of $$G$$ with size $$i$$, and $$\gamma_1(G)$$ is the edge domination number of $$G$$. In this paper, we obtain some properties of the coefficients of the edge domination polynomial of $$G$$ and show that the edge domination polynomial of $$G$$ is equal to the vertex domination polynomial of line graph $$L(G)$$ of $$G$$.
##### MSC:
 05C31 Graph polynomials 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)