NEW COUNTING FORMULA FOR DOMINATING SETS IN PATH AND CYCLE GRAPHS

Abstract

Let G=(V(G), E(G)) be a path or cycle graph. A subset D of V(G) is a dominating set of G if for every u element of V(G)\D, there exists v element of D such that uv element of E(G), that is, N[D]=V(G). The domination number of G, denoted by gamma(G), is the smallest cardinality of a dominating set of G. A set D_1 subset of V(G) is a set containing dominating vertices of degree 2, that is, each vertex is internally stable. A set D_2 subset of V(G) is a set containing dominating vertices where one of the element say a element of D_2,  and the rest are of degree 2. A set  D_3 subset of V(G) is a set containing dominating vertices in which two of the elements say b, c element of D_3, deg(b)=deg(c)=1. This paper developed a new combinatorial formula that determines the number of ways of putting a dominating set in a path and cycle graphs of order n>=1 and n>=3, respectively. Further, a combinatorial function P^1_G(n),  P^2_G(n) and P^3_G(n) that determines the probability of getting the set D_1, D_2, and D_3, respectively in graph G of order n were constructed.