Graphs with minimum degree-entropy

Yanni Dong, Maximilien Gadouleau, Pengfei Wan, Shenggui Zhang

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Article number120629
JournalInformation Sciences
Volume671
DOIs
StatePublished - Jun 2024

Keywords

  • Complexity measure
  • Extremal value
  • Graph entropy

Fingerprint

Dive into the research topics of 'Graphs with minimum degree-entropy'. Together they form a unique fingerprint.

Cite this