|
|
|
|
|
Volume 37 • Number 1 • 2014 |
|
•
The Generalized Connectivity of Complete Equipartition 3-Partite Graphs
Shasha Li, Wei Li and Xueliang Li
Abstract.
Let G be a nontrivial connected graph of order n, and k an integer with 2≤k≤n. For a set S of k vertices of G, let κ(S) denote the maximum number ℓ of edge-disjoint trees T1,T2,…,Tℓ in G such that V(Ti)∩V(Tj)=S for every pair of distinct integers i,j with 1≤i,j≤ℓ.Chartrand \emph{et al.} generalized the concept of connectivity as follows: The k-connectivity of G, denoted by κk(G), is defined by κk(G)=min{κ(S)}, where the minimum is taken overall k-subsets S of V(G). Thus κ2(G)=κ(G), where κ(G) is the connectivity of G; whereas, κn(G) is the maximum number of edge-disjoint spanning trees contained in G.
This paper mainly focuses on the k-connectivity of complete equipartition 3-partite graphs K3b, where b≥2 is an integer. First, we obtain the number of edge-disjoint spanning trees of a general complete 3-partite graph Kx,y,z, which is ⌊(xy+yz+zx)/(x+y+z−1)⌋. Then, based on this result, we get the k-connectivity of K3b for all 3≤k≤3b.
2010 Mathematics Subject Classification: 05C40, 05C05
Full text: PDF
|
|
|
|
|
|
|
|
|