A note on the domination entropy of graphs

‎A dominating set of a graph G is a subset D of vertices such that every vertex outside D has a neighbor in D‎. ‎The domination number of G‎, ‎denoted by \gamma(G)‎, ‎is the minimum cardinality amongst all dominating sets of G‎. ‎The domination entropy of G‎, ‎denoted by I_{dom}(G) is defined as I_{dom}(G)=-\sum_{i=1}^k\frac{d_i(G)}{\gamma_S(G)}\log (\frac{d_i(G)}{\gamma_S(G)})‎, ‎where \gamma_S(G) is the number of all dominating sets of G and d_i(G) is the number of dominating sets of cardinality i‎. ‎A graph G is C_4-free if it does not contain a 4-cycle as a subgraph‎. ‎In this note we first determine the domination entropy in the graphs whose complements are C_4-free‎. ‎We then propose an algorithm that computes the domination entropy in any given graph‎. ‎We also consider circulant graphs G and determine d_i(G) under certain conditions on i‎.

A note on the domination entropy of graphs Keywords:

Information‎ , ‎Domination polynomial‎ , ‎domination entropy‎ , ‎algorithm‎ , ‎circulant graph