پیوندهای مفید
آمار
| تعداد نشریات | 11 |
| تعداد شماره‌ها | 227 |
| تعداد مقالات | 2,310 |
| تعداد مشاهده مقاله | 3,587,446 |
| تعداد دریافت فایل اصل مقاله | 2,628,905 |
A note on the domination entropy of graphs | ||
| Journal of Discrete Mathematics and Its Applications | ||
| مقاله 2، دوره 10، شماره 1، خرداد 2025، صفحه 11-20 اصل مقاله (282.47 K) | ||
| نوع مقاله: Full Length Article | ||
| شناسه دیجیتال (DOI): 10.22061/jdma.2025.11448.1106 | ||
| نویسندگان | ||
| Arezoo N. Ghameshlou* 1؛ Mana Mohammadi2؛ Amirhesam JafariRad2 | ||
| 1Department of Irrigation and Reclamation Engineering University of Tehran, P. O. Box 4111, Karaj, 31587–77871, I. R. Iran | ||
| 2Department of Electrical Engineering, University of Tehran Tehran, I. R. Iran | ||
| تاریخ دریافت: 21 آبان 1403، تاریخ بازنگری: 07 بهمن 1403، تاریخ پذیرش: 08 بهمن 1403 | ||
| چکیده | ||
| 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$. | ||
| کلیدواژه‌ها | ||
| Information؛ domination polynomial؛ domination entropy؛ algorithm؛ circulant graph | ||
| مراجع | ||
|
[1] S. Akbari, S. Alikhani, and Y. H. Peng, Characterization of graphs using domination polynomials, Eur. J. Comb. 31 (2010) 1714–1724.https://doi.org/10.1016/j.ejc.2010.03.007
[2] S. Alikhani, Y.H. Peng, Dominating sets and domination polynomial of paths, Int. J. Math. Math. Sci. (2009) 542040.https://doi.org/10.1155/2009/542040
[3] S. Alikhani, Y.H. Peng, Dominating sets and domination polynomial of cycles, Glob. J. Pure Appl. Math. 4(2) (2008) 151–162.https://doi.org/10.48550/arXiv.0905.3268
[4] S. Alikhani, J.I. Brown, S. Jahari, On the domination polynomials of friendship graphs, Filomat 30(1) (2016) 169–178.https://doi.org/10.2298/fil1601169a
[5] M. Bayati, R. Keshavan, A. Montanari, S. Oh and A. Saberi, Generating random Tannergraphs with large girth, 2009 IEEE Information Theory Workshop, Taormina, Italy, 2009, 154157.https://doi.org/10.1109/itw.2009.5351491
[6] B. Bollobas and E. Szemeredi, Girth of sparse graphs, J. Graph Theory 39 (2002) 194200.https://doi.org/10.1002/jgt.10023
[7] S. Cao, M. Dehmer, Z. Kang, Network entropies based on independent sets and matchings, Appl. Math. Comput. 307 (2017) 265–270.https://doi.org/10.1016/j.amc.2017.02.021
[8] S. Cao, M. Dehmer, Y. Shi, Extremality of degree-based graph entropies, Inf. Sci. 278 (2014) 2233.https://doi.org/10.1016/j.ins.2014.03.133
[9] M. Dehmer, Information processing in complex networks: graph entropy and information functionals, Appl. Math. Comput. 201 (2008) 82–94.https://doi.org/10.1016/j.amc.2007.12.010
[10] M. Dehmer, A. Mowshowitz, A history of graph entropy measures, Inf. Sci. 181 (2011) 5778.https://doi.org/10.1016/j.ins.2010.08.041
[11] P. Frankl, Cops and robbers in graphs with large girth and Cayley graphs, Discrete Appl. Math. 17 (1987) 301–305.https://doi.org/10.1016/0166-218x(87)90033-3
[12] C. Gao, S. Liu, D. Jiang, L. Chen, Constructing LDPC Codes with Any Desired Girth, Sensors (2021) 21(6): 2012. https://doi.org/10.3390/s21062012
[13] M.Ghorbani, M.Dehmer,A.Mowshowitz,J.Tao,F.Emmert-Streib, TheHosoyaentropyofgraphs revisited, Symmetry 11(8) (2019) 1013.https://doi.org/10.3390/sym11081013
[14] N. Rashevsky, Life, information theory and topology, Bull. Math. Biophys. 17 (1955) 229235.https://doi.org/10.1007/bf02477860
[15] C. Shannon, W. Weaver, Mathematical Theory of Communications, University of Illinois, Urbana, 1949.https://doi.org/10.4324/9781003432272-6
[16] B. Sahin, New network entropy: The domination entropy of graphs, Inf. Process. Lett. 174 (2022) 106195.https://doi.org/10.1016/j.ipl.2021.106195
[17] B. Sahin, A. Sahin, On domination polynomials of caterpillar graphs, Turk. J. Math. Comput. Sci. 9 (2018) 34–38.https://dergipark.org.tr/tr/download/article-file/607652
[18] S. Wagner, I. Gutman, Maxima and minima of the Hosoya index and the Merrifield-Simmons index, Acta Appl. Math. 112 (2010) 323–346.https://doi.org/10.1007/s10440-010-9575-5
[19] P. Wan, X. Chen, J. Tu, M. Dehmer, S. Zhang, F. Emmert-Streib, On graph entropy measures based on the number of independent sets and matchings, Inf. Sci. 516 (2020) 491504.https://doi.org/10.1016/j.ins.2019.11.020 | ||
|
آمار تعداد مشاهده مقاله: 289 تعداد دریافت فایل اصل مقاله: 226 |
||