Dominating sets and domination polynomial of complete graphs with missing edges

Abstract EN

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

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

Let kn be complete graph with order n.

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

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

Using this recursive formula, we consider the polynomial D (K_n,x), ∑_i^n▒〖=1〗 d (K_n,i) Xi which we call domination polynomial of complete graphs and obtain some properties of this polynomial.