The Tree Connectivity Of Several Graphs

Today's society is a complex system of different networks,all kinds of networks can be easily modeled as an undirected graph,directed graph,weighted graph or random graph and so on.Therefore,many research topics related to the network can be transformed into some graph theory problems,such as the reliability problem of the network can be transformed into the reliability parameter problem of the graph,such as the connectivity of the graph,steiner tree packing number and tree connectivity and so on.Connectivity is one of the basic concept of graph theory,which can be used to measure a performance of the communication network.It is convenient to use a graph to describe a communication network,if the connectivity of a graph is high,the greater the possibility that the network will work in the event of a failure of the vertex and edge of the graph,that is to say,the network's reliability is the better.In recent years,mathematicians have introduced new connectivity concepts,such as conditional connectivity and tree connectivity and so on,and the connectivity of graphs is studied from different angles.This paper mainly studies the tree connectivity of several graphs.Given a connected graph G and let S be a set of at least two vertices in a graph G.A subtree T of G is an S-Steiner tree if S (?) V(T).Two S-Steiner trees T₁ and T₂ are internally disjoint if E(T₁)(?) E(T₂)=(?) and V(T₁)(?) V(T₂)=S.Similarly,Two S-Steiner trees T₁ and T₂ are edge-disjoint if E(T₁)(?) E(T₂)=(?).?_G(S)(?_G(S))be the maximum number of internally disjoint(edge-disjoint)S-Steiner trees in G,and let ?_k(G)(?_k(G))be the minimum ?_G(S)(?_G(S))for S ranges over all k-subsets of V(G).In this paper,we mainly study the relation between the generalized connectivity of line graph and the generalized edge connectivity of the original graph,and around the following conjecture put forward by Li et al.:?_k(L(G))??_k(G)for integer k?2 and a graph G with at least k vertices.We get the following results:(1)This problem is studied by the maximum average degree and we establish an inequality ?_k(L(G))??_k(G)-[[mad(G)/2]/2]for general k,where mad(G)is the maximum average degree of a graph G.We also show that ?_k(L(G))??_k(G)-[[r/2/2]]for any integers k and r such that k ?(r2);(2)We determine that the conjecture holds for k=5;(3)The wheel graph and the complete bipartite graph K_3,n satisfy the conjecture.In addition,we also study the ?₃-connectivity of Cartesian product of complete graphs,determine K₃(K_n1?K_n2)=n₁+n₂-3 for any two complete graphs,(?) for any k complete graphs.