A note on the domination entropy of graphs

Ghameshlou, Arezoo N.; Mohammadi, Mana; JafariRad, Amirhesam

doi:10.22061/jdma.2025.11448.1106

A note on the domination entropy of graphs

Document Type : Full Length Article

Authors

¹ Department of Irrigation and Reclamation Engineering University of Tehran, P. O. Box 4111, Karaj, 31587–77871, I. R. Iran

² Department of Electrical Engineering, University of Tehran Tehran, I. R. Iran

10.22061/jdma.2025.11448.1106

Abstract

‎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$‎.

Graphical Abstract