Graph entropy and related topics
Yanni Dong is a PhD student in the research group Formal Methods and Tools. Her supervisors are prof.dr. H.J. Broersma from the faculty of Electrical Engineering, Mathematics and Computer Science and prof.dr. S. Zhang from the Northwestern Polytechnical University, China.
This thesis focuses on extremal problems involving various graph parameters that were introduced in graph theory motivated by the well-known Shannon entropy in information theory. In particular, new results are obtained for extremal problems involving degree-based and distance-based entropies. Moreover, results on the computational complexity of decision and optimization problems concerning maximum and minimum spanning trees for graphical function indices are derived. Determining extremal values of topological indices and the extremal graphs that attain these values is a popular research direction within graph theory.
In Chapter 1 of this thesis we give a general introduction to this theme, together with some historical background and an overview of the contributions from this thesis. One of the approaches is to look at the effect of certain graph operations on the value of such indices. This approach is particularly useful if the extremal graphs can be obtained through a series of graph operations.
In Chapter 2, we consider the effect of graph operations, including concepts like the weak product, the blow-up and the identification of vertices, on the degree-based entropy.
In Chapter 3 to Chapter 5, we study extremal problems involving the degree-based entropy restricted to some specific graph classes. In Chapter 3, we focus on trees and unicyclic graphs, and determine the maximum and minimum values of the degree-based entropy under some given parameters, including the diameter and a given bipartition. This is mainly done by analyzing the effect of graph operations on the degree-based entropy.
Chapter 4 studies the extremal values of the degree-based entropy of bipartite graphs, using the representation of bipartite graphs by Young diagrams. We prove that the extremal graph attaining the minimum value is a complete bipartite graph or nearly complete bipartite graph. We show that the general problem of characterizing the extremal graphs is related to a very complicated problem in number theory. Therefore, we believe that this problem is difficult to solve. Among bipartite graphs with a given order and size, we use the degree sequence to characterize the extremal graphs attaining the maximum value of the degree-based entropy. We extend these results to some generalized graphical function indices. We prove that the difference between the maximum degree and the minimum degree of the degree sequence of the extremal graphs does not exceed 2.
In Chapter 5, we fully characterize the extremal graphs for which the degree-based entropy attains the minimum value among all graphs with a given order and size. The extremal graphs turn out to be special so-called threshold graphs.
In Chapter 6, we study two kinds of distance-based entropies, namely the eccentricity-entropy and the Wiener-entropy. By deriving the (asymptotic) extremal behavior, we conclude that the Wiener-entropy of graphs of a given order is more spread than the eccentricity-entropy. We resolve three known conjectures on the eccentricity-entropy and propose two new conjectures on the Wiener-entropy, which we formulate at the end of this summary.
In Chapter 7, we study the computational complexity of decision and optimization problems concerning maximum and minimum spanning trees for graphical function indices that are computable in polynomial time. Among trees of a given size and order, many topological indices attain either their maximum or minimum value for the unique case that the tree is a path. We show that either the maximum or the minimum spanning tree problems for such topological indices are N P -complete. We also prove that if the corresponding functions are strictly convex or concave, then the minimum and maximum spanning tree problems for these graphical function indices are N P-complete, and their optimization versions are APX-complete, respectively.
Although this thesis contains many new results, several questions and conjectures remain open. One of the challenging open problems is to fully characterize the bipartite graphs of a given size and order which minimize the degree-based entropy. Apart from the open problems in the thesis, there are still many other problems to be explored and solved involving graph entropies. In this sense, the results of this thesis are only the tip of the iceberg.