Loading [MathJax]/jax/output/HTML-CSS/jax.js
top library bulletin
bar home editorial guideline content
dot
 
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 2kn. 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 1i,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 b2 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+z1). Then, based on this result, we get the k-connectivity of K3b for all 3k3b.

2010 Mathematics Subject Classification: 05C40, 05C05


Full text: PDF
 
dot