Graph entropy and related topics

This thesis consists of an introductory chapter (Chapter 1), followed by six technical chapters. These six chapters have been written in the style of journal papers, based on the five joint papers. The presented results of this thesis deal with graph entropy, a concept in chemical graph theory inspired by the well-known Shannon entropy in information theory. In fact, the thesis focuses on different variants of graph entropy, mainly on degree-based and distance-based entropies. Apart from Chapter 5, the other chapters of the thesis are mainly based on the research results that the author obtained when she was working as a joint Ph.D. candidate at Northwestern Polytechnical University in Xi’an, P.R. China and the University of Twente in Enschede, the Netherlands. Chapter 2 studies the effect of graph operations on the degree entropy. The results of this chapter provide tools for the research on follow-up extremal problems on degree entropy. Chapter 3 to Chapter 5 mainly deal with extremal problems involving the degree entropy restricted to specific graph classes. Chapter 5 is based on research that was carried out while the author was visiting the Algorithms and Complexity group in the Computer Science department of Durham University in Durham, UK. Chapter 6 addresses extremal problems involving two important distance-based entropies: eccentricity-entropy and Wiener entropy. Chapter 7 studies the computational complexity of spanning tree problems for graphical function indices. These indices unify a large number of well-studied topological indices originating from chemical graph theory, and are closely related to degree-based graph entropies.