A note on the domination entropy of graphs
نویسندگان
1 Department of Electrical Engineering, University of Tehran Tehran, I. R. Iran
2 Department of Electrical Engineering, University of Tehran Tehran, I. R. Iran
3 Department of Irrigation and Reclamation Engineering University of Tehran, P. O. Box 4111, Karaj, 31587–77871, I. R. Iran
doi
10.22061/jdma.2025.11448.1106چکیده
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$.
