Study On The Cover Cost And The Reverse Cover Cost Of Graphs

Extremal graph theory has been the focus of graph theory research,and it has been widely used in chemistry,computer science,biology.The structure of extremal graph of figure parameter has always been a hot topic.More and more attention is paid to how to find the graph structure of some special graph classes,especially to study particular figure parameter or graph invariants which can describe the maximum or minimum.Figure parameter and graph invariants lay a theoretical foundation and provide a mathematical model for describing the differences of molecular structures and properties and the stability of computer networks.In this paper,the cover cost and the reverse cover cost of graphs are studied,the relation between them and graph structure is established by algebraic method.The main contents of this paper are as follows:In chapter 1,we firstly introduce some important concepts and symbols used in this paper,secondly introduce the research background and current situation of this paper,and finally propose the main results.In chapter 2,we characterized the unique tree with minimum cover cost among all trees of arbitrary degree sequence,where the cover cost of a vertex v in G is defined as CCG(v)=(?)Hvu,where Hvu is the expected hitting time for random walk beginning at v to visit u.In this paper,we use the property of greedy tree,graph transformation method to describe the polar graph of the minimum cover cost of arbitrary degree sequence tree.The main conclusions are:Take the longest path in the optimal tree,and let U1 be the branch with the most points among the branches of the longest path.W1 is a branch adjacent to U1 and W2.The number of vertices of branch W1 is less than or equal to the number of vertices of U1 and greater than the number of vertices of other branches.U2 is a branch adjacent to U1 and U3.The number of vertices of U2 is less than or equal to that of W1,and greater than that of other branches.Then,the relationship between the number of vertices in each branch on the road is:|V(U1)|≥|V(W1)|≥|V(U2)|≥|V(W2)|≥…≥|V(Um)|=|V(Wm)|=1;The relation between the degree of each vertex is:|d(u1)|≥|d(w1)|≥|d(u2)|≥|d(w2)|≥…|d(um)|=|d(wm)|=1.Finally,we proved that among trees of given degree sequence with the minimum cover cost is the greedy tree.In chapter 3,we study the tree with the degree sequence(m,2,…,2,1,…,1)(the multiplicity of 1 is m).we get another tree by moving pendent vertex of the longest segment to pendent vertex of the shortest segment for any tree.By comparing the reverse cover cost of the former tree and the latter tree,a extremal tree with the minimum the reverse cover cost is determined,and the vertex of the minimum reverse cover cost is also given.In chapter 4,we summarize the research content of this paper and propose further research directions.