Some Topics On The Generalized Connectivity

Steiner trees are widely used in VLSI circuit design.For a given terminal node,Steiner tree would be used to transfer and share an electronic signal.It has a vital effect on computer communication networks and optical wireless communication networks.The key scientific problem to be solved is to find effective research tools.The Nash-Williams-Tutte theorem is the most classical result of spanning trees.By apply-ing the Menger theorem and other tools,we can find pendant S-Steiner trees and Stein-er paths in the figure.The most basic products in graph theory are Cartesian product,dictionary product,strong product,and direct product.Product networks are based on the idea that two known networks are combined using graph products so that the new network inherits some properties of the known network.The research on this problem will provide theoretical support for product network research.In order to obtain the bounds of the generalized(edge)connectivity of cluster,corona,join and Cartesian product,it is necessary to find an appropriate tree decomposition method.That is,de-compose the product graph into several different types of small graphs,and regroup all the small graphs.Next,we combine each set of different types of small graphs into the desired Steiner tree structure.When the upper bound of f(n;τ3(G)=1),n=5,6,7,8 equal sign holds,we explore the method of deleting edges from the complete graph to reach its critical edge number,at the same time,through the graph of small vertices,to summarize the law of reaching a specific value of the graph class.In this thesis,we obtain exact values of generalized(edge-)connectivity for clus-ter;sharp upper and lower bounds of generalized(edge-)connectivity for join and corona.Next,we consider the sharp lower bounds of generalized edge connectivity of Cartesian product graphs.In the end,we also study that maximum generalized local connectivity,f(n;τk(G)=l)=max{e(G)||V(G)|=n,τk(G)=l}.We obtain the upper bound of f(n;τk(G)=0),k=n-1,n;f(n;τk(G)=0),3 ≤k≤n-3;and f(n;τ3(G)=1),n=5,6,7,8.When the upper bound equal sign holds,the extreme graph is characterized.