Journal
GRAPHS AND COMBINATORICS
Volume 33, Issue 5, Pages 1195-1209Publisher
SPRINGER JAPAN KK
DOI: 10.1007/s00373-017-1837-9
Keywords
Generalized 3-connectivity; Cayley graphs; Transposition trees; Modified bubble; sort graphs
Categories
Funding
- National Natural Science Foundation of China [11301480, 11201021]
- Natural Science Foundation of Ningbo, China [2017A610132]
- Zhejiang Provincial Natural Science Foundation of China
- Natural Science Foundation of Tianjin [17JCQNJC00300]
- BUCT Fund for Disciplines Construction and Development [1524]
Ask authors/readers for more resources
The generalized connectivity of a graph is a natural generalization of the connectivity and can serve for measuring the capability of a network G to connect any k vertices in G. Given a graph and a subset of at least two vertices, we denote by the maximum number r of edge-disjoint trees in G such that for any pair of distinct integers i, j, where . For an integer k with , the generalized k-connectivity is defined as . That is, is the minimum value of over all k-subsets S of vertices. The study of Cayley graphs has many applications in the field of design and analysis of interconnection networks. Let Sym(n) be the group of all permutations on and be a set of transpositions of Sym(n). Let be the graph on n vertices such that there is an edge ij in if and only if the transposition . If is a tree, we use the notation to denote the Cayley graph on symmetric groups generated by . If is a cycle, we use the notation to denote the Cayley graph on symmetric groups generated by . In this paper, we investigate the generalized 3-connectivity of T-n and MBn and show that kappa(3) (T-n) = n - 2 and kappa(3) (MBn) = n - 2.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available