Graphs with minimum degree-entropy

Dong, Yanni; Gadouleau, Maximilien; Wan, Pengfei; Zhang, Shenggui

Abstract

We continue studying extremal values of the degree-entropy, which is an information-theoretic measure defined as the Shannon entropy based on the information functional involving vertex degrees. For a graph with a given number of vertices and edges achieving the minimum entropy value, we show its unique structure. Also, a tight lower bound for the entropy in bipartite graphs with a given number of vertices and edges is proved. Our result directly derives the result of Cao et al. (2014) that for a tree with a given number of vertices, the minimum value of the entropy is attained if and only if the tree is the star.

Citation

Dong, Y., Gadouleau, M., Wan, P., & Zhang, S. (2024). Graphs with minimum degree-entropy. Information Sciences, 671, 120629. https://doi.org/10.1016/j.ins.2024.120629

• Journal Article Type: Article
• Acceptance Date: Apr 10, 2024
• Online Publication Date: Apr 30, 2024
• Publication Date: 2024-06
• Deposit Date: Jun 7, 2024
• Publicly Available Date: Jun 7, 2024
• Journal: Information Sciences
• Print ISSN: 0020-0255
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 671
• Pages: 120629
• DOI: https://doi.org/10.1016/j.ins.2024.120629
• Public URL: https://durham-repository.worktribe.com/output/2475188