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=۱}^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_۴-free if it does not contain a ۴-cycle as a subgraph‎. ‎In this note we first determine the domination entropy in the graphs whose complements are C_۴-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‎.

کلیدواژه ها:

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