| تعداد نشریات | 13 |
| تعداد شمارهها | 238 |
| تعداد مقالات | 2,418 |
| تعداد مشاهده مقاله | 3,962,359 |
| تعداد دریافت فایل اصل مقاله | 2,874,083 |
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؛ Amirhesam Jafari-Rad2؛ Mana Mohammadi2 | ||
| 1Department of Irrigation and Reclamation Engineering University of Tehran, P. O. Box 4111, Karaj, 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 γ(G), is the minimum cardinality amongst all dominating sets of G. The domination entropy of G, denoted by Idom(G) is defined as Idom(G)=-∑i=1kdi(G)/γS(G)log (di(G)/γS(G)), where γS(G) is the number of all dominating sets of G and di(G) is the number of dominating sets of cardinality i. A graph G is C4-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 C4-free. We then propose an algorithm that computes the domination entropy in any given graph. We also consider circulant graphs G and determine di(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, 154-157. https://doi.org/10.1109/itw.2009.5351491
[6] B. Bollobas and E. Szemeredi, Girth of sparse graphs, J. Graph Theory 39 (2002) 194-200. 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) 22-33. 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) 57-78. 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) 229-235. 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) 491-504. https://doi.org/10.1016/j.ins.2019.11.020 | ||
|
آمار تعداد مشاهده مقاله: 376 تعداد دریافت فایل اصل مقاله: 281 |
||