The vertex domination polynomial and edge domination polynomial of a graph. (English) Zbl 1274.05230

Askari, Bahman; Alaeiyan, Mehdi

Acta Univ. Apulensis, Math. Inform. 28, 157-162 (2011).

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.)

Keywords:

vertex domination polynomial of a simple graph; edge domination polynomial of a simple graph; coefficients