The Count Of The Subtree Of The Graph

Graph theory is a new and rapidly developing discipline.It has many links with computers,chemistry,physics and so on.It has attracted the attention of many scholars at home and abroad.This paper mainly investigates the number of subtrees of graphs.The main contents are divided into the following two parts:Firstly,the second chapter investigates the tree structure with the most Pk in the tree set whose vertex number is n≥k.When k = 2r is an even number,the tree T with vertex number n contains Pk at most「(n-2r+2)/2」「(n-2r+2)/2」,we also characterize the structure of the tree corresponding to the number「(n-2r+2)/2」「(n-2r+2)/2」.When k = 2r + 1 is an odd number,there is an integer t ∈[2,(n-1)/r],the tree T with vertex number n contains Pk at most Fn,k,t =(s 2)(q + 1)2 +(ts 2)q2 + s(t-s)q(q +1),where the integers n,t,q,s satisfies n-((k-1)/2-1)t-1 = tg + s,0 ≤ s<t,and we characterize the structure of the tree that corresponds to the extreme value reached.In particular,when k = 5,characterize the extremal tree which contain the most number of P5.Second,the third chapter investigates the number of subtrees in some graphs,including the maximum and minimum values of the number of subtrees of a graph with given number of edges,and we characterize the largest,the smallest number of subtrees of graph.We also characterize the structure of the tree given degree sequence with the most number of P4.