您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2022, Vol. 57 ›› Issue (11): 42-49.doi: 10.6040/j.issn.1671-9352.0.2021.518

• • 上一篇    

折叠超立方体的广义3-连通度

王军震1,张淑敏1,2*,葛慧芬3   

  1. 1.青海师范大学数学与统计学院, 青海 西宁 810008;2.高原科学与可持续发展研究院, 青海 西宁 810008;3.青海师范大学计算机学院, 青海 西宁 810008
  • 发布日期:2022-11-10
  • 作者简介:王军震(1993— ),男,硕士研究生,研究方向为组合数学与图论.E-mail:wangjunzhen2021@126.com*通信作者简介:张淑敏(1971— ),女,博士,教授,研究方向为组合数学与图论.E-mail:zhangshumin@qhnu.edu.cn
  • 基金资助:
    青海省自然科学基金资助项目(2019-ZJ-921)

Generalized 3-connectivity of folded hypercubes

WANG Jun-zhen1, ZHANG Shu-min1,2*, GE Hui-fen3   

  1. 1. College of Mathematics and Statistics, Qinghai Normal University, Xining 810008, Qinghai, China;
    2. Academy of Plateau, Science and Sustainability, Xining 810008, Qinghai, China;
    3. College of Computing, Qinghai Normal University, Xining 810008, Qinghai, China
  • Published:2022-11-10

PDF (PC)

305

摘要： 设图G是一个连通图,S⊆V(G)。图G的一棵S-斯坦纳树是一棵包含S中所有顶点的树T=(V ',E '),使得S⊆V '。如果连接S的两棵斯坦纳树T和T ',满足E(T)∩E(T ')=且V(T)∩V(T ')=S,则称T和T '是内部不交的。定义κ(S)为图G中内部不相交S-斯坦纳树的最大数目。广义k-连通度(2≤k≤n)定义为κk(G)=min{κ(S)|S⊆V(G)且|S|=k},显然,κ2(G)=κ(G)。证明了κ3(FQn)=n,其中FQn是n-维折叠超立方体。

关键词: 广义连通度, 斯坦纳树, 折叠超立方体

Abstract: Let G be a connected graph and S⊆V(G). T=(V ',E ')is an S-Steiner tree which containing all the vertices in is S of G and make S⊆V '. Two S-trees T and T ' are said to be internally disjoint if E(T)∩E(T ')= and V(T)∩V(T ')=S. κ(S)is defined as the maximum number of the internally disjoint S-trees in G. The generalized k-connectivity(2≤k≤n)κk(G)of G is defined as κk(G)=min{κ(S)|S⊆V(G)and |S|=k}. Clearly, κ2(G)=κ(G). κ3(FQn)=n is proved where FQn is n-dimensional folded hypercube.

Key words: generalized connectivity, Steiner tree, folded hypercube

中图分类号: 

  • O157
[1] BONDY J A, MURTY U S R. Graph Theory[M]. New York: Spring, 2008.
[2] WHINEY H. Congruent graphs and connectivity of graphs[J]. Math Soc, 1932, 54:150-168.
[3] CHARTRAND G, KAPOOR S F, LESNINK L. Generalized connectivity in graphs[J]. Bombay Math, 1984, 2:1-6.
[4] SUN Yuefang, LI Xueliang, MAO Yapin, et al. Note on the generalized connectivity[J]. ARS Combinatoria: An Australian-Canadian Journal of Combinatorics, 2014, 114:193-202.
[5] LI Shasha, LI Xueliang, ZHOU Wenli. Sharp bounds for the generalized connectivity κ3(G)[J]. Discrete Math, 2010, 310:2147-2163.
[6] LI Hengzhe, MENG Jixiang, MA Yingbin, et al. Steiner tree packing number and tree connectivity[J]. Discrete Math, 2018, 341:1945-1951.
[7] CHARTRAND G, OKAMOTO F, ZHANG Ping. Rainbow trees in graphs and generalized connectivity[J]. Networks, 2010, 55(4):360-367.
[8] LI Hengzhe, LI Xueliang, SUN Yuefang. The generalized 3-connectivity of Cartesian product graphs[J]. Discrete Math Theor Comput Sci, 2012, 14(1):43-54.
[9] LI Hengzhe, MA Yingbin, YANG Weihua. The generalized 3-connectivity of graph products[J]. Appl Math Comput, 2017, 295:77-83.
[10] LI Shasha, LI Wei, LI Xueliang. The generalized connectivity of complete bipartite graphs[J]. ARS Combin, 2012, 104:65-79.
[11] ZHAO Shuli, HAO Rongxia, WU Jie. The generalized 3-connectivity of some regular networks[J]. Parallel Distrib Comput, 2019, 133:18-29.
[12] ZHAO Shuli, HAO Rongxia, WU Jie. The generalized connectivity of (n,k)-bubble-sort graphs[J]. Comput, 2019, 62:1277-1283.
[13] ZHAO Shuli, HAO Rongxia. The generalized connectivity of alternating group graphs and(n,k)-star graphs[J]. Discrete Appl Math, 2018, 251:310-321.
[14] LI Shasha, SHI Yongtang, TU Jianhua. The generalized 3-connectivity of cayley graphs on symmetric groups generated by trees and cycles[J]. Graphs Combin, 2017, 33:1195-1209.
[15] LIN Shangwei, ZHANG Qianhua. The generalized 4-connectivity of hypercubes[J]. Discret Appl Math, 2017, 220:60-67.
[16] ZHAO Shuli, HAO Rongxia, CHENG E. Two kinds of generalized connectivity of dual cubes[J]. Discret Appl Math, 2019, 257:306-316.
[17] ZHAO Shuli, HAO Rongxia, WU Jie. The generalized 4-connectivity of hierarchical cubic networks[J]. Discret Appl Math, 2021, 289:194-206.
[18] LI Xueliang, MAO Yaping. A survey on the generalized connectivity of graphs[J/OL]. arXiv: 1207.1838.
[19] AMAWY E, ATIFI A. Properties and performance of folded hypercubes[J]. IEEE Transactions on Parallel and Distributed Systems, 1991, 2(1):131-142.
[20] LIU Jiabao, PAN Xiangfeng, CAO Jinde. Some properties on Estrada index of folded hypercubes networks[J]. Abstract and Applied Analysis, 2014: 1-6.
[21] PARK J S, DAVIS N J. The folded hypercube ATM switches[C] //The Proceedings of IEEE International Conference on Networking, Part II. [S.l.] :[s.L] , 2001: 370-379.
[22] PARK J S, DAVIS N J. Modeling the folded hypercube ATM switches[C] //The Proceedings of OPNETWORK. [S.l.] :[s.L] , 2001.
[23] LATIFI S. Simulation of PM21 network by folded hypercube[J]. IEE Proc E Comput Digit Tech, 1991, 138(6):397-400.
[24] ESMAEILI T, LAK G, RAD A N. 3D-FolH-NOC: a new structure for parallel processing and distributed systems[J]. Comput, 2012, 4(6):163-168.
[25] ZHANG Mimi, ZHOU Jinxin. On g-extra connectivity of folded hypercubes[J]. Theoretical Computer Science, 2015, 593:146-153.
[1] 解承玲, 马海成. 两个点并路的匹配等价图类[J]. 《山东大学学报(理学版)》, 2021, 56(1): 29-34.
[2] 李晶晶,边红,于海征. 亚苯基链的修正互惠度距离指标[J]. 《山东大学学报(理学版)》, 2020, 55(10): 71-76.
[3] 魏宗田,方慧,李银奎. 基于网络选址的设施系统可靠性[J]. 《山东大学学报(理学版)》, 2020, 55(10): 77-82.
[4] 刘佳,孙磊. 不含4-圈或弦6-圈的平面图是(3,0,0)-可染的[J]. 《山东大学学报(理学版)》, 2018, 53(12): 31-40.
[5] 陈洪玲,王慧娟,高红伟. 可嵌入到欧拉示性数非负的曲面图的线性荫度[J]. 《山东大学学报(理学版)》, 2018, 53(12): 17-22.
[6] 包丽娅,陈祥恩,王治文. 完全二部图K10,n(10≤n≤90)的点可区别E-全染色[J]. 《山东大学学报(理学版)》, 2018, 53(12): 23-30.
[7] 张友,黄丽娜,李沐春. 一类六角系统的点可区别边染色[J]. 《山东大学学报(理学版)》, 2018, 53(12): 41-47.
[8] 李美莲,邓青英. 平图的transition多项式的Maple计算[J]. 山东大学学报（理学版）, 2018, 53(10): 27-34.
[9] 寇艳芳,陈祥恩,王治文. K1,3,p和 K1,4,p的点可区别的IE-全染色及一般全染色[J]. 山东大学学报（理学版）, 2018, 53(8): 53-60.
[10] 刘小花,马海成. Q形图的匹配能序及Hosoya指标排序[J]. 山东大学学报（理学版）, 2018, 53(8): 61-65.
[11] 张江悦,徐常青. 最大平均度不超过4的图的线性2-荫度[J]. 山东大学学报（理学版）, 2018, 53(6): 7-10.
[12] 曹亚萌,黎娇,李国全. 有限域上的和集与子空间的平移[J]. 山东大学学报（理学版）, 2018, 53(4): 7-10.
[13] 陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报（理学版）, 2017, 52(12): 36-41.
[14] 何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报（理学版）, 2017, 52(10): 24-30.
[15] 李亭亭,劳会学. 一类混合型数论函数的均值估计[J]. 山东大学学报（理学版）, 2017, 52(8): 70-74.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发