Construction of Dominating Sets of Certain Graphs

Abstract EN

Let G be a simple graph.

A set S⊆V is a dominating set of G, if every vertex in V∖S is adjacent to at least one vertex in S.

We denote the family of dominating sets of a graph G with cardinality i by ?(G,i).

In this paper we introduce graphs with specific constructions, which are denoted by G(m).

We construct the dominating sets of G(m) by dominating sets of graphs G(m−1), G(m−2), and G(m−3).

As an example of G(m), we consider ?(Pn,i).

As a consequence, we obtain the recursive formula for the number of dominating sets of G(m).