Dominating sets and domination polynomial of k_r-gluingof graphs

Abstract EN

Let G=(V, E) be a simple graph.

Aset D⊆V is a dominating set of G, if every vertex in V-D is adjacent to at least one vertex in D.

Let G be k_r-gluing of G_1 and G_2and denote by C[G_1 ∪_r G_2] the family of all k_r-gluing of G_1and G_2.

Let K_t be complete graph with order t and K_m be complete graph with order m and let G be k_r-gluing of K_t and K_m with order n=m+t-r.

Let G_n^i be the family of dominating sets of G_n with cardinality i, and let d(G_n, i)=|G_n^i |.

In this paper, we construct G_n^i, and obtain a recursive formula for d(G_n, i).

Using this recursive formula, we consider the polynomial D(G_n, x)=∑_(i=1)^n▒〖d(G_n, i)x_i 〗, which we call domination polynomial of k_r-gluing of graphs and obtain some properties of this polynomial.