Extremal values of degree-based entropies of bipartite graphs
From MaRDI portal
Publication:6400895
arXiv2206.00922MaRDI QIDQ6400895FDOQ6400895
Authors: Stijn Cambie, Yan-Ni Dong, Matteo Mazzamurro 
Publication date: 2 June 2022
Abstract: We characterize the bipartite graphs that minimize the (first-degree based) entropy, among all bipartite graphs of given size, or given size and (upper bound on the) order. The extremal graphs turn out to be complete bipartite graphs, or nearly complete bipartite. Here we make use of an equivalent representation of bipartite graphs by means of Young tableaux, which make it easier to compare the entropy of related graphs. We conclude that the general characterization of the extremal graphs is a difficult problem, due to its connections with number theory, but they are easy to find for specific values of the order and size . We also give a direct argument to characterize the graphs maximizing the entropy given order and size. We indicate that some of our ideas extend to other degree-based topological indices as well.
Has companion code repository: https://github.com/matteomazzamurro/extrema-graph-entropy
Graph theory (including graph drawing) in computer science (68R10) Measures of information, entropy (94A17) Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Extremal problems in graph theory (05C35) Vertex degrees (05C07)
This page was built for publication: Extremal values of degree-based entropies of bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6400895)
