您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2022, Vol. 57 ›› Issue (6): 44-53.doi: 10.6040/j.issn.1671-9352.0.2021.718

• • 上一篇    

关于图运算的基于度的图熵

吴传书1,3,赵海兴2,3,邓波1,3*   

  1. 1.青海师范大学数学与统计学院, 青海 西宁 810008;2.青海师范大学计算机学院, 青海 西宁 810008;3.藏语智能信息处理及应用国家重点实验室, 青海 西宁 810008
  • 发布日期:2022-06-10
  • 作者简介:吴传书(1997— ),男,硕士研究生,研究方向为图论及其应用. E-mail:wuchuanshu2021@163.com *通信作者简介:邓波(1983— ),男,博士,教授,研究方向为图论及其应用. E-mail:dengbo450@163.com
  • 基金资助:
    高等学校学科创新引智计划资助(D20035);青海省藏文信息处理与机器翻译重点实验室(2020-ZJ-Y05)

Degree-based graph entropy on graph operations

WU Chuan-shu1,3, ZHAO Hai-xing2,3, DENG Bo1,3*   

  1. 1. College of Mathematics and Statistics, Qinghai Normal University, Xining 810008, Qinghai, China;
    2. College of Computer, Qinghai Normal University, Xining 810008, Qinghai, China;
    3. The State Key Laboratory of Tibetan Intelligent Information Processing and Application, Xining 810008, Qinghai, China
  • Published:2022-06-10

PDF (PC)

320

摘要： 研究在对称差、笛卡尔积、张量积、冠积运算下的基于度的图熵计算,以及运用这些结果来计算纳米结构和超立方体分子图的基于度的图熵。

关键词: 图运算, 图熵, 香农熵, 顶点度, 分子图

Abstract: Graph invariants are widely used to construct entropy-based metrics to describe the structures of complex networks. In particular, graph entropy based on vertex degrees is often used to measure graph structure information after graph operations.The degree-based graph entropy calculation on some graph operations containing the symmetric difference, Cartesian product, tensor product, Corona product of graphs are presented. These results are applied to calculate the degree-based graph entropy of molecular graphs such as nano-structure and hypercubes.

Key words: graph operation, graph entropy, Shannon entropy, vertex degree, molecular graph

中图分类号: 

  • O157.5
[1] SHANNON C E, WEAVER W. The mathematical theory of communication[M]. Urbana: University of Illinois Press, 1949.
[2] RASHEVSKY N. Life, information theory, and topology[J]. The Bulletin of Mathematical Biophysics, 1955, 17(3):229-235.
[3] TRUCCO E. A note on the information content of graphs[J]. The Bulletin of Mathematical Biophysics, 1956, 18(2):129-135.
[4] MOWSHOWITZ A. Entropy and the complexity of graphs: I. an index of the relative complexity of a graph[J]. The Bulletin of Mathematical Biophysics, 1968, 30(1):175-204.
[5] MOWSHOWITZ A. Entropy and the complexity of graphs: II. the information content of digraphs and infinite graphs[J]. The Bulletin of Mathematical Biophysics, 1968, 30(2):225-240.
[6] MOWSHOWITZ A. Entropy and the complexity of graphs: III. graphs with prescribed information content[J]. The Bulletin of Mathematical Biophysics, 1968, 30(3):387-414.
[7] MOWSHOWITZ A. Entropy and the complexity of graphs: IV. entropy measures and graphical structure[J]. The Bulletin of Mathematical Biophysics, 1968, 30(4):533-546.
[8] KÖRNER J. Coding of an information source having ambiguous alphabet and the entropy of graphs[C] // 6th Prague Conference on Information Theory. [S.l.] : Walter. de. Gruyter, 1973: 411-425.
[9] LU G X, LI B Q, WANG L J. Some new properties for degree-based graph entropies[J]. Entropy, 2015, 17(12):8217-8227.
[10] CAO S J, DEHMER M, SHI Y T. Extremality of degree-based graph entropies[J]. Information Sciences, 2014, 278:22-33.
[11] DONG Y N, QIAO S N, CHEN B, et al. Maximum values of degree-based entropies of bipartite graphs[J]. Applied Mathematics and Computation, 2021, 401:126094.
[12] DEHMER M. Information processing in complex networks: graph entropy and information functionals[J]. Applied Mathematics and Computation, 2008, 201(1/2):82-94.
[13] DEHMER M, MOWSHOWITZ A. A history of graph entropy measures[J]. Information Sciences, 2011, 181(1):57-78.
[14] YEGNANARAYANAN V, THIRIPURASUNDARI P R, PADMAVATHY T. On some graph operations and related applications[J]. Electronic Notes in Discrete Mathematics, 2009, 33:123-130.
[15] FATH-TABAR G H, VAEZ-ZADEH B, ASHRAFI A R, et al. Some inequalities for the atom-bond connectivity index of graph operations[J]. Discrete Applied Mathematics, 2011, 159(13):1323-1330.
[16] KHALIFEH M H, YOUSEFI-AZARI H, ASHRAFI A R. Vertex and edge PI indices of Cartesian product graphs[J]. Discrete Applied Mathematics, 2008, 156(10):1780-1789.
[17] KHALIFEH M H, YOUSEFI-AZARI H, ASHRAFI A R. The Hyper-Wiener index of graph operations[J]. Computers & Mathematics with Applications, 2008, 56(5):1402-1407.
[18] KHALIFEH M H, YOUSEFI-AZARI H, ASHRAFI A R. The first and second Zagreb indices of some graph operations[J]. Discrete Applied Mathematics, 2009, 157(4):804-811.
[19] YERO I G, RODRÍGUEZ-VELÁZQUEZ J A. On the Randic index of corona product graph[J]. International Scholarly Research Notices, 2011, 2011:262183.
[20] GHORBANI M, DEHMER M, ZANGI S. Graph operations based on using distance-based graph entropies[J]. Applied Mathematics and Computation, 2018, 333:547-555.
[21] BONDY J A, MURTY U S R. Graph theory[M]. New York: Springer, 2008.
[22] DEHMER M, VARMUZA K, BORGERT S, et al. On entropy-based molecular descriptors: statistical analysis of real and synthetic chemical structures[J]. Journal of Chemical Information and Modeling, 2009, 49(7):1655-1663.
[23] DEHMER M, SELVAGANESH L, VARMUZA K. Uniquely discriminating molecular structures using novel eigenvalue-based descriptors[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2012, 67(1):147-172.
[24] IMRICH W, KLAV S. Zar: product graphs: structure and recognition[M]. New York: John Wiley & Sons, 2000.
[25] NAJI A M, SONER N D. The first leap Zagreb index of some graph operations[J]. International Journal of Applied Graph Theory, 2018, 2(1):7-18.
[26] ASHRAFI A R, DOŠLIC T, HAMZEH A. The Zagreb coindices of graph operations[J]. Discrete Applied Mathematics, 2010, 158(15):1571-1578.
[27] RANI A, IMRAN M, ALI U. Sharp bounds for the inverse sum indeg index of graph operations[J]. Mathematical Problems in Engineering, 2021, 2021:5561033.
[1] 解承玲, 马海成. 两个点并路的匹配等价图类[J]. 《山东大学学报(理学版)》, 2021, 56(1): 29-34.
[2] 李晶晶,边红,于海征. 亚苯基链的修正互惠度距离指标[J]. 《山东大学学报(理学版)》, 2020, 55(10): 71-76.
[3] 魏宗田,方慧,李银奎. 基于网络选址的设施系统可靠性[J]. 《山东大学学报(理学版)》, 2020, 55(10): 77-82.
[4] 陈洪玲,王慧娟,高红伟. 可嵌入到欧拉示性数非负的曲面图的线性荫度[J]. 《山东大学学报(理学版)》, 2018, 53(12): 17-22.
[5] 刘佳,孙磊. 不含4-圈或弦6-圈的平面图是(3,0,0)-可染的[J]. 《山东大学学报(理学版)》, 2018, 53(12): 31-40.
[6] 包丽娅,陈祥恩,王治文. 完全二部图K10,n(10≤n≤90)的点可区别E-全染色[J]. 《山东大学学报(理学版)》, 2018, 53(12): 23-30.
[7] 张友,黄丽娜,李沐春. 一类六角系统的点可区别边染色[J]. 《山东大学学报(理学版)》, 2018, 53(12): 41-47.
[8] 李美莲,邓青英. 平图的transition多项式的Maple计算[J]. 山东大学学报（理学版）, 2018, 53(10): 27-34.
[9] 刘小花,马海成. Q形图的匹配能序及Hosoya指标排序[J]. 山东大学学报（理学版）, 2018, 53(8): 61-65.
[10] 寇艳芳,陈祥恩,王治文. K1,3,p和 K1,4,p的点可区别的IE-全染色及一般全染色[J]. 山东大学学报（理学版）, 2018, 53(8): 53-60.
[11] 陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报（理学版）, 2017, 52(12): 36-41.
[12] 何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报（理学版）, 2017, 52(10): 24-30.
[13] 李亭亭,劳会学. 一类混合型数论函数的均值估计[J]. 山东大学学报（理学版）, 2017, 52(8): 70-74.
[14] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报（理学版）, 2017, 52(8): 100-106.
[15] 王晔,孙磊. 不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报（理学版）, 2017, 52(4): 34-39.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发