×

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.)
PDF BibTeX XML Cite