[1]张 燕,马木提·阿依古丽*.由轮生成的Cayley图的广义3-连通度[J].四川师范大学学报(自然科学版),2020,43(03):345-349.[doi:10.3969/j.issn.1001-8395.2020.03.009]
 ZHANG Yan,MAMUT Aygul.The Generalized 3-Connectivity of Cayley Graphs Generated by Wheel Graphs[J].Journal of SichuanNormal University,2020,43(03):345-349.[doi:10.3969/j.issn.1001-8395.2020.03.009]
点击复制

由轮生成的Cayley图的广义3-连通度()
分享到:

《四川师范大学学报(自然科学版)》[ISSN:1001-8395/CN:51-1295/N]

卷:
43卷
期数:
2020年03期
页码:
345-349
栏目:
基础理论
出版日期:
2020-05-05

文章信息/Info

Title:
The Generalized 3-Connectivity of Cayley Graphs Generated by Wheel Graphs
文章编号:
1001-8395(2020)03-0345-05
作者:
张 燕 马木提·阿依古丽*
新疆大学 数学与系统科学学院, 新疆 乌鲁木齐 830046
Author(s):
ZHANG Yan MAMUT Aygul
College of Mathematics and System Sciences, Xinjiang University, Urumqi 830046, Xinjiang
关键词:
Cayley图 广义k-连通度 内部不交的S-树
Keywords:
Cayley graph generalized k-connectivity internally disjoint S-tree
分类号:
O157.5
DOI:
10.3969/j.issn.1001-8395.2020.03.009
文献标志码:
A
摘要:
令SV(G),κG(S)表示图G中内部不交的S-树T1,T2,…,Tr的最大数目r,使得对任意i,j∈{1,2,…,r}且i≠j,有V(Ti)∩V(Tj)=S,E(Ti)∩E(Tj)=.定义κk(G)=min{κG(S)|SV(G),且|S|=k}为图G的广义k-连通度,其中k是整数
Abstract:
Let SV(G) and κG(S) denote the maximum number r of internally disjoint S-trees T1,T2,…,Tr in graph G such that V(Ti)∩V(Tj)=S and E(Ti)∩E(Tj)= for any i,j∈{1,2,…,r} and i≠j. For an integer k with 2≤k≤n, the generalized k-connectivity of a graph G is defined as κk(G)=min{κG(S)|SV(G) and |S|=k}. Let Sym(n) be the symmetric group on {1,2,…,n} and T be a set of transpositions of Sym(n). Denote by G(T) the graph with vertex set {1,2,…,n} and edge set {ij|(ij)∈T}. If G(T) is a wheel graph, then simply denote the Cayley graph Cay(Sym(n),T) by WGn. In this paper, we study the generalized 3-connectivity of Cayley graphs generated by wheel graphs WGn, and prove that κ3(WGn)=2n-3, where n≥4.

参考文献/References:

[1] BONDY J A, MURTY U S R. Graph Theory[M]. New York:Springer-Verlag,2008:213-214.
[2] WHITNEY H. Congruent graphs and the connectivity of graphs[J]. American J Mathematics,1932,54(1):150-168.
[3] CHARTRAND G, KAPOOR S, LESNIAK L, et al. Generalized connectivity in graphs[J]. Bull Bombay Mathematic Colloquim,1984,2:1-6.
[4] LI S. Note on the hardness of generalized connectivity[J]. J Combinatorial Optimization,2012,24(3):389-396.
[5] LI S, LI X, ZHOU W. Sharp bounds for the generalized connectivity κ3(G)[J]. Discrete Mathematics,2010,310(15/16):2147-2163.
[6] LI H, MA Y, YANG W, et al. The generalized 3-connectivity of graph products[J]. Applied Mathematics Computation,2017,295:77-83.
[7] LI S, TU J, YU C. The generalized 3-connectivity of star graphs and bubble-sort graphs[J]. Applied Mathematics Computation,2016,274:41-46.
[8] LI S, SHI Y, TU J. The generalized 3-connectivity of Cayley graphs on symmetric groups generated by trees and cycles[J]. Graphs Combinatorics,2017,33(5):1-15.
[9] LIN S, ZHANG Q. The generalized 4-connectivity of hypercubes[J]. Discrete Applied Mathematics,2017,220:60-67.
[10] SHI H. On conjectures of interconnection networks[J]. Computer Engineering Applications,2008,44(31):112-115.
[11] TU J, ZHOU Y, SU G. A kind of conditional connectivity of Cayley graphs generated by wheel graphs[J]. Applied Mathematics and Computation,2017,301:177-186.

备注/Memo

备注/Memo:
收稿日期:2018-12-21 接受日期:2019-04-04 基金项目:国家自然科学基金(11361060和11701492) *通信作者简介:马木提·阿依古丽(1968-),女,教授,主要从事图论及其应用的研究,E-mail:aygul@xju.edu.cn
更新日期/Last Update: 2020-05-05