Structure And The Number Of Subtrees Of Graphs

In the field of graph theory, it is a very important and active problem to determine the range of many invariants in some classes of graphs and characterize the extremal graphs. Generally speak-ing, for many classes graphs (especially trees), the extremal one that minimizes the number of subtrees is exactly the one that maximizes some chemical indices such as the well-known Wiener index, and vice versa. However, a counter example has showed that no’nice’func-tional relationship exits between these two concept. Therefore, it is not easy to decide the extremal graphs which maximize (minimize) the number of subtrees. In recent decades, although there are many good results on the number of subtrees, up to now, it is still no hope to solve completely this problem. In this thesis, we mainly investi-gate properties of the number of subtrees of a tree with given degree sequence by theoretical arguments and algorithmic approach.First, we investigate extremal maximum problems about the number of subtrees of a tree with given degree sequence with two ap-proaches. On the one hand, with the method of structural analysis, we obtain some properties of the number of subtrees of a tree with given degree sequence. These results are used to characterize trees with the given degree sequence that have the largest number of sub-trees, which are greedy trees. Given two different degree sequences π and π1. If π(?)π1, then the number of subtrees of the greedy tree Tπ*is less than the number of subtrees of Tπ1. Then we generalize the re-cent results of Kirk and Wang. These trees coincide with those which were proven by Wang and independently Zhang et al. to minimize the Wiener index. We also provide a partial ordering of the extremal trees with different degree sequences, some extremal results follow as corrollaries. One the other hand, we take an algorithmic approach by which we characterize the trees which maximize the number of subtrees. And it explicitly describes the process of achieving an ex-tremal tree from any random tree among trees of a given order and degree sequence. The result also leads to some interesting questions and provides insight on finding the trees close to extremal and their numbers of subtrees.Second, we nationally investigate the structures of an extremal tree which has the minimal number of subtrees in the set of all trees with the given degree sequence of a tree. In particular, the mini-mal trees must be caterpillar. In addition, we study the structures of optimal trees in the set of all caterpillars with the given degree sequence.These results are used to determine the all extremal trees which has the minimum number of subtrees in the set of all trees of order n with the maximum degree△and in the set of all trees with a given degree sequence π=(d1,…, d5,1,…,1), respectively. In the end,we investigate the minimum optimal trees with many leaves and find it is difficult to determine the ultima structures.